You are currently browsing geomblog’s articles.

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

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

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

1. Nondeterministic time hierarchies
It’s common to think about a machine as a black box: send inputs in at one end, and out comes the decision at the other end. This way of thinking about machines runs into trouble when you work with nondeterminism. Remember that a nondeterministic machine accepts if there is some way of making guesses so that it accepts. This yields two ways of thinking about how a nondeterministic machine operates:

  • The Many-worlds model: the machine tries all possibilities and outputs 1 if some possibility leads to 1.
  • The Guess-and-check mode: the machine guesses the right answer and runs it (checks) through its program.

Now consider what needs to happen if you want to accept the complement of a language accepted by an NDTM. For a deterministic machine this is easy. just flip the accepting and rejecting states of the machine, and you’ll accept the complement of the language. But for an NDTM this doesn’t work ! In the many worlds interpretation, a string that’s accepted might have many accepting possibilities and many rejecting possibilities, so if you merely flip bits, an NDTM will accept the string as before. In the guess-and-check model, you have to argue that there is no way of finding a guess that works.

So accepting the complement of a language is tricky when you’re being nondeterministic (in time). This is the question of whether NP = co-NP (for bounded time), and in general is the question of whether exhaustive search can be avoided. But more immediately, it causes problems for diagonalization, because the key step where you flip the outcome of running M_x(x) cannot be performed. That’s what makes proving the hierarchy theorem for nondeterministic time so tricky.

Bizarrely though, this argument doesn’t work for nondeterministic SPACE. In fact, a famous result by Savitch shows that
\displaystyle NSPACE(f^2) \subseteq DSPACE(f), directly implying that NPSPACE = PSPACE. It’s worth thinking about why this might be so, and where our intuition from above breaks down.

2. Ladner’s theorem.
The two time hierarchy theorems operate in a single mode: determinism or non-determinism. Similarly for space hierarchy theorems. If we actually want to prove that P != NP via diagonalization, we need some way of ‘bridging the gap’ between determinism and non-determinism, and here is where the importance of Ladner’s result comes in.

Hierarchy theorems for deterministic time and space, and for nondeterministic time. Details can be found in Chapter 3 of the Arora-Barak book.

Points to consider:

  • Why is it harder to diagonalize nondeterministic machines
  • How does the efficiency of simulation affect the bounds

We’d like to know whether P = NP or not. In other words, we want to be able to simulate non determinism with determinism. What’s the easiest thing we can do ? we can try “all guesses”: roughly, this leads to a bound of the form \displaystyle {c(M)^{t(n)}} if t(n) is the running time of the nondeterministic machine.

Dick Lipton has a proof on his blog of a much stronger result of the form
{c^{t(n)}}, where c is INDEPENDENT of the nondeterministic machine.

He also has a general conjecture that might be provable:

For any \epsilon > 0,
NTIME(f(n)) \subseteq TIME(2^{\epsilon f(n)})

in other words, maybe it’s exponentially faster, but in a tiny way. I encourage you to read the post, understand the theorem, and think about this conjecture. Note that proving the conjecture doesn’t lead to anything earth shattering, but it would be a neat result to have.

Points to ponder:

Speedup theorem:

There exists a (total computable) predicate P such that for any algorithm computing P(x) with running time T(x), there exists another algorithm computing P(x) with computation time O(ln T(x)).

Gap theorem:

For any computable unbounded r(n) there exist a computable time bound t(n) such that any language
computable in time t(n) is also computable in time r(t(n)).

How do these results gel with our sense that problems should have intrinsic running times ? what’s the catch ?