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

Google Wave

Saturday, November 14th, 2009

用了一阵Google Wave了。当然还是有很多bug。但是也有一些不错的功能。最重要的是非常强大的扩展功能。比如现在的 \LaTeX 实现就是一个扩展。

最常见的扩展有三种(严格的说只有两种)。Gadget, extension和bot。Gadget可以直接插入到wave当中,比如map或者sudoku;在对话参与者中加入bot可以自动修改某些对话内容,比如LaTeXy。Extension相当于扩展了wave的界面,可以和gadget或者bot结合。




Wednesday, November 4th, 2009

科学结果都是peer reviewed。就是说评定科学成果的人必须也是从事同样工作的。


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