From the ArXiv: http://arxiv.org/abs/0907.3965

It’s a draft, but contains much of what we’ve been talking about re: circuit lower bounds.

Lance Fortnow has a new blog post about “Nondeterministic NC.” He responds to a reader question:

Can we define a class NNC such that NC ⊆ RNC ⊆ NNC. Is NNC known by some other name? It is clear that NNC ⊆ NP, but the reverse is not obvious.

We are not meeting tomorrow (Thursday), as Suresh is still ill with a mystery bug. We will reconvene Monday (June 22). I have updated the Wiki.

Hi all,
I’ve posted the reading for Monday Jun 15. We’ll continue with circuits, specifically chapter 13.2 in the online draft (the proof that PARITY cannot be computed with a poly-size circuit family that includes MOD(3) gates).

I don’t know if we’ll be able to get through the entire proof on Monday. Let’s see how far we can go.

• Let U be a unary language (it consists of strings of the form $1^i$). Show that if U is NP-Complete, then P = NP.
• Construct a decidable language in P/poly that is NOT in P
• If P = NP, then there’s a language in EXP that requires exponential circuits. For this problem you’ll need the result
$EXP \subseteq P/poly \Rightarrow EXP = \Sigma^p_2$. Note the paradoxical nature of the result: an upper bound (P = NP) implies a lower bound. For the definition of $\Sigma^p_2$, see this chapter.

Dick Lipton has a perfectly timed post on why he doesn’t like oracle proofs. Makes for excellent reading.

It might be helpful to ponder exercises 6/7 in the notes. Specifically:

• Show that there is an oracle A and a language $L \in NP^A$ such that L is not polynomial-time reducible to 3SAT even when the machine computing the reduction is allowed access to A
• Suppose we pick a random language B, by deciding for each string independently and with probability 1/2 whether or not it is in B. Show that with high probability $P^B \ne NP^B$

Just thought I’d mention that Scott Aaronson has a post on his blog about “proofs that should finish with a gong […] instead of a QED symbol”. Theorem 2 is IMO the most ridiculous of them all, giving an explicit algorithm for any NP-complete problem that runs in polynomial time if P=NP (!).

Please read the section in the diagonalization chapter on oracle machines, and the Baker-Gill-Solovay result.