You are currently browsing the tag archive for the ‘diagonalization’ tag.

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

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.