Skip to content

Latest commit

 

History

History
36 lines (29 loc) · 1.29 KB

Complexity.page

File metadata and controls

36 lines (29 loc) · 1.29 KB

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$