NNC

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.

Monday: Nondeterministic time hierarchies and Ladner’s theorem

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 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
, 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.

Readings for Thursday

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

Simulating nondeterminism

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 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
, where c is INDEPENDENT of the nondeterministic machine.

He also has a general conjecture that might be provable:

For any ,

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.