### Complexity Theory Side Note

Saturday, November 21st, 2009I am currently reading the book: Computational Complexity: A Modern Approach. I have taken some side notes while reading. I will update the nodes here since I also found some other interesting related materials online.

**Chapter 1**

- I don’t feel the definition of
*time constructible function*satisfiable. The possible gaps to fill in may be the conditions and properties of such functions. This concept is important for time hierarchical theorem. Question 3.5 is related. - Here is a blog post by Dick Lipton about oblivious Turing machine. This definition is later used for proving Cook-Levin Theorem. Exercise 1.5 and 1.6 can help understand the machine.
- On the philosophy issue, another blog post by Daniel Lemier is interesting.
- Typos: page16 line 2 in definition of time-constructible functions should be: “the function …”; page 24 line 2: “Note that we …” should be “We note that …”.

A time line of some important results in first several chapters:

- Space/Time Hierarchy Theorem [SHL65] [HS65]
- Savitch’s Theorem [Sav70] : implies PSPACE = NPSPACE
- Cook-Levin Theorem [Coo71] [Lev73]: SAT is NP-complete
- Nondeterministic Time Hierarchy Theorem [Coo72]
- Ladner’s Theorem [Lad75]: If NP P, exist that is not NP-complete.
- Immerman-Szelepcsenyi Theorem [Imm88] [Sze87]: , which implies NL = coNL.

(to be continued…)