# 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

- #P-complete

- #P ???
*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*

- aka the
- 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

- favorite pastime: compute \Sigma(n), S(n) by hand
- 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