Complexity

TODO merge in notes from CS172

  • classes
    • #P ???
      • #P-complete
        • counting reductions
        • contains some easy P problems
      • eg: dnf-sat, 2sat, permanent of a matrix, number of perfect matchings for a bipartite graph
  • kolmogorov complexity of a string is min len of computer programming (in some universal lang) to output that string

On Non-Computable Functions (Tibor Rado 1962)

  • used TMs
  • \Sigma(n): max length of computation by a TM of size n
    • aka the Busy Beaver function
  • S(n): max length of computation by a TM of size n that eventually stops
  • Busy Beaver game: try to make TMs of a given size that ran for as long as possible (but stopped)
  • led to a slew of papers about busy beavers
    • favorite pastime: compute \Sigma(n), S(n) by hand
      • requires analyzing all TMs of given size to figure out whether it stops
      • if so, how long it runs, and what number it prints
  • article

Computer Studies of Turing Machine Problems (Rado, Shen Lin, 1965)

  • computer analyzez easy machines; hard ones by hand
  • proved \Sigma(1) = 1, S(1) = 1, \Sigma(2) = 4, S(2) = 6
  • Lin’s PhD thesis: \Sigma(3) = 6, S(3) = 21
  • Allen Brady, 1983: \Sigma(4) = 13, S(4) = 107