## Complexity Theory Side Note

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**

- 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…)

November 23rd, 2009 at 1:05 pm

Thanks for pointer to my post.

I am curious about your reading their new book. I plan to use it, how is the book overall?

November 23rd, 2009 at 4:58 pm

Here are some pros and cons comes to my mind instantly. Note I only read about 1/3 of the book.

Pros:

1) It covers a broad spectrum of topics.

2) There are a lot high level discussions which gives me a aerial viewpoint. I think this is import since I can see connections between different areas and understand what are really important things.

3) This book is quite up to date.

Cons:

1) Many typos. I think it is because it is quite new.

2) Some proofs are not “standard”, e.g. Cook-Levin theorem, Ladner’s theorem, etc. By standard, I mean the original proof by the discoverer. This is also the case for some definitions. However some may think different viewpoint is a merit.

3) Compared with some other proof writer, I found the proofs in the book are less easier to follow. The overall quality are good though.