"Intuitive" is hard because some of these results are pretty nonintuitive. I'll just tackle the relativization barrier.
The Baker-Gill-Solovay theorem is that there is some oracle A "relative to which" PA=NPAPA=NPA and a different oracle B, for which PB≠NPBPB≠NPB. What does this formalism mean? Normally when we talk about the complexity class PP it refers to languages recognized by Turing machines in a polynomially-bounded amount of time.. But for PAPA, the Turing machine has a subroutine (the oracle) which can recognize any language AA, or a class of languages AA, in one step.
For example, P3SATP3SAT is the complexity class of languages which a Turing machine can recognize in polynomial time, if it has access to a magic 3SAT solver. This complexity class is at least as large as NP, since 3SAT is NP-complete. PPPP is an example of using an entire class as the oracle, rather than an individual language.
What the theorem showed is that an oracle for TQBF (True Quantified Boolean Formulas) is strong enough to make PTQBF=NPTQBFPTQBF=NPTQBF. TQBF instances are logical formulae containing existential and universal quantifiers--- that is, statements like "for all X, there exists Y and Z, such that X and Y imply not-Z". TQBF is a PSPACE-complete problem.
The details are technical but basically the proof looks like NPTQBF⊆NPSPACETQBF⊆NPSPACE=PSPACE⊆PTQBFNPTQBF⊆NPSPACETQBF⊆NPSPACE=PSPACE⊆PTQBF. TQBF doesn't add anything to NPSPACE (nondeterministic polynomial space); a previous theorem shows NPSPACE = PSPACE; but because TQBF is NPSPACE-complete, a Turing machine with access to an TQBF oracle must be at least as strong as PSPACE.
The other half of the theorem is coming up with an oracle B that definitively makes nondeterminism stronger, so that PB≠NPBPB≠NPB. The general approach is to define a very simple language: SL(B)SL(B) which recognizes all strings exactly the same length as something in language B! (Which we haven't defined yet.) Obviously an nondeterminstic Turing machine can just "guess" some word of the right length and then use the B-oracle to verify that the word is in B. The hard part of the proof is coming up with some B that a deterministic Turing machine can't generate the inputs to, in polynomial time--- so the oracle doesn't help. The proof uses diagonalization, but the details are really hairy.
OK, so what does that show?
What the theorem gives us is that any "proof" or proof technique for P=NPP=NP or P≠NPP≠NP that isn't sensitive to the presence of an oracle, cannot work. That's because we showed that, depending on the oracle, the two could be equal or not equal.
Suppose a colleague slips us a paper purporting to show P≠NPP≠NP. We can search-and-replace every occurrence of PP by PTQBFPTQBF and NPNP by NPTQBFNPTQBF. Now obviously the proof must now be flawed, because the substituted classes are equal. So (if the proof is correct) somewhere it must make use of a property of PP that is not true of PTQBFPTQBF.
"Duh!" you might say. Well, there is one very common proof technique which relativizes (i.e it is not sensitive to the presence of an oracle): Diagonalization.
The Time Hierarchy Theorem was proven using diagonalization. It says, roughly, that for every big-O time class, there are problems that take at least that much time on a Turing machine. So there are problems that take O(n5000)O(n5000) time to solve but can't be solved in O(n4999)O(n4999). The proof is equally valid if we substitute in a Turing machine with an oracle! Even our monster PTQBFPTQBF has problems that can be solved in O(n2)O(n2) but not in O(n)O(n).
Simple diagonalization is essentially a "counting" argument, which doesn't depend on the structure of the problems involved, only the final result. And thus it can't solve P vs. NP. (More sophisticated versions of the proof technique exist, though.)
An analogy that may be helpful is proving statements about numbers. There are some statements you can prove about integers that are independent of whether you're working in ZZ or in ZmodpZmodp. For example, we can show that 2+2=2∗22+2=2∗2 in any number system obeying the usual definitions of addition and multiplication. But in some systems 2+3≠02+3≠0 and in other systems 2+3=02+3=0. Thus, our number theory proofs "relativize" if they are ignorant of the "mod p" but are "nonrelativizing" if they depend on the particular modulus, or lack thereof.
The Baker-Gill-Solovay theorem is that there is some oracle A "relative to which" PA=NPAPA=NPA and a different oracle B, for which PB≠NPBPB≠NPB. What does this formalism mean? Normally when we talk about the complexity class PP it refers to languages recognized by Turing machines in a polynomially-bounded amount of time.. But for PAPA, the Turing machine has a subroutine (the oracle) which can recognize any language AA, or a class of languages AA, in one step.
For example, P3SATP3SAT is the complexity class of languages which a Turing machine can recognize in polynomial time, if it has access to a magic 3SAT solver. This complexity class is at least as large as NP, since 3SAT is NP-complete. PPPP is an example of using an entire class as the oracle, rather than an individual language.
What the theorem showed is that an oracle for TQBF (True Quantified Boolean Formulas) is strong enough to make PTQBF=NPTQBFPTQBF=NPTQBF. TQBF instances are logical formulae containing existential and universal quantifiers--- that is, statements like "for all X, there exists Y and Z, such that X and Y imply not-Z". TQBF is a PSPACE-complete problem.
The details are technical but basically the proof looks like NPTQBF⊆NPSPACETQBF⊆NPSPACE=PSPACE⊆PTQBFNPTQBF⊆NPSPACETQBF⊆NPSPACE=PSPACE⊆PTQBF. TQBF doesn't add anything to NPSPACE (nondeterministic polynomial space); a previous theorem shows NPSPACE = PSPACE; but because TQBF is NPSPACE-complete, a Turing machine with access to an TQBF oracle must be at least as strong as PSPACE.
The other half of the theorem is coming up with an oracle B that definitively makes nondeterminism stronger, so that PB≠NPBPB≠NPB. The general approach is to define a very simple language: SL(B)SL(B) which recognizes all strings exactly the same length as something in language B! (Which we haven't defined yet.) Obviously an nondeterminstic Turing machine can just "guess" some word of the right length and then use the B-oracle to verify that the word is in B. The hard part of the proof is coming up with some B that a deterministic Turing machine can't generate the inputs to, in polynomial time--- so the oracle doesn't help. The proof uses diagonalization, but the details are really hairy.
OK, so what does that show?
What the theorem gives us is that any "proof" or proof technique for P=NPP=NP or P≠NPP≠NP that isn't sensitive to the presence of an oracle, cannot work. That's because we showed that, depending on the oracle, the two could be equal or not equal.
Suppose a colleague slips us a paper purporting to show P≠NPP≠NP. We can search-and-replace every occurrence of PP by PTQBFPTQBF and NPNP by NPTQBFNPTQBF. Now obviously the proof must now be flawed, because the substituted classes are equal. So (if the proof is correct) somewhere it must make use of a property of PP that is not true of PTQBFPTQBF.
"Duh!" you might say. Well, there is one very common proof technique which relativizes (i.e it is not sensitive to the presence of an oracle): Diagonalization.
The Time Hierarchy Theorem was proven using diagonalization. It says, roughly, that for every big-O time class, there are problems that take at least that much time on a Turing machine. So there are problems that take O(n5000)O(n5000) time to solve but can't be solved in O(n4999)O(n4999). The proof is equally valid if we substitute in a Turing machine with an oracle! Even our monster PTQBFPTQBF has problems that can be solved in O(n2)O(n2) but not in O(n)O(n).
Simple diagonalization is essentially a "counting" argument, which doesn't depend on the structure of the problems involved, only the final result. And thus it can't solve P vs. NP. (More sophisticated versions of the proof technique exist, though.)
An analogy that may be helpful is proving statements about numbers. There are some statements you can prove about integers that are independent of whether you're working in ZZ or in ZmodpZmodp. For example, we can show that 2+2=2∗22+2=2∗2 in any number system obeying the usual definitions of addition and multiplication. But in some systems 2+3≠02+3≠0 and in other systems 2+3=02+3=0. Thus, our number theory proofs "relativize" if they are ignorant of the "mod p" but are "nonrelativizing" if they depend on the particular modulus, or lack thereof.
No comments:
Post a Comment