## Archive for November, 2009

### Complexity Theory Side Note

Saturday, November 21st, 2009

I 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

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.
2. 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.
3. On the philosophy issue, another blog post by Daniel Lemier is interesting.
4. Typos: page16 line 2 in definition of time-constructible functions should be: “the function $|x| \to \llcorner T(|x|) \lrcorner$ …”; 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 $\neq$ P, exist $L \in NP \setminus P$ that is not NP-complete.
• Immerman-Szelepcsenyi Theorem [Imm88] [Sze87]: $\overline{\text{PATH}} \in \text{NL}$, which implies NL = coNL.

(to be continued…)

Saturday, November 14th, 2009

### 科学和艺术的一个区别

Wednesday, November 4th, 2009

Science is what we understand well enough to explain to a computer. Art is everything else we do.
— Knuth