You are currently browsing the category archive for the ‘lectures’ category.

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.

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