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 ?

Hi all,
I was thinking that it might be useful for any of you to have the ability to post to the blog (that is, not just comment). Anyone with a profile on wordpress.com can be added as a contributor, so if you have a profile, let me know (post a comment here) and I’ll add you as a contributor.

Hi all
Welcome to the P vs NP seminar. This will be the main place for posting readings for upcoming lectures, and for discussions. General information about the course will continue to be posted at the seminar home page.