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

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

2 Responses to “Complexity Theory Side Note”

  1. rjlipton Says:

    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?

  2. liuchuan Says:

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

    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.

    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.

Leave a Reply