Why is SAT &lem S, S spare , implies P=NP interesting? important? (Henceforth Mahaney's thm.) I'm not trying to convince you that it is, I am asking if it is. Here are some thoughts.
- The original motivation is the Berman-Hartmanis conjecture that all NP complete sets are poly-isom. Mahaney's thm is a consequence of the conjecture. One could do the BH paper and show why it is plausible and then give this result. But is it worth it?
- The result is a stepping stone to Karp-Lipton's result that SAT &leT S, S sparse, implies PH collapses. This begs the question- why is KL important? Because it is a stepping stone for Yap's result that SAT &isin coNP/poly implies PH collapses. And why is that important? Because it is used in the proof that if GI is NPC then PH collapses. This is good enough for me- evidence that a natural problem is NOT NPC-- surely worth knowing. But do we need to present Mahaney's result to get to Yap's result?
- Should point out that KL is also interesting because it is a link between uniform and non-uniform complexity. But again, perhaps we could do that without Mahaney's result.
- The techniques used to prove Mahaney's result are interesting and lead to other theorems of interest. Like what? Well, ur, the Ogiwara-Watnabe result which replaces &lem with &lebtt. And the result of Lozano that generalizes this to other classes like MODaSAT (number of assignments is &equiv 0 mod a). Why are these of interest? I have an intuitive sense that they are, but I can't even really say why theorists find it interesting. For that matter, do theorists find it interesting? (This was discussed in this blog entry, though the discussion was derailed by someone asking an off-topic question.)
Here's some old-school intuition: since we believe P != NP and we know SAT is NP-complete, we believe that SAT is a "complex" set. In some sense, a sparse problem is not very complex, as it has so few positive instances. The theorem formalizes the above intuition: if we could faithfully map this seemingly complex set into a sparse set, we would have P = NP.
ReplyDeleteI'm just a youngun, so my history could be off, but it seems Mahaney's result is one of several from a period where people were trying to point to specific properties that make problems like SAT hard. (Its density is apparently at least one factor.)
I think the general project of showing that unlikely-sounding complexity assumptions would collapse the PH is worth emphasizing even to non-theorists. However, I think for such a course, Mahaney's theorem is too specialized--clever in a way too specific to itself and its extensions (you might want to show the easier result for coNP, though).
ReplyDeleteWhat I would focus on, after Karp-Lipton, is PH collapses that work thru Arthur-Merlin protocols, since these protocols are both inherently intriguing and historically very fruitful.
Graph isomorphism of course has interesting AM protocols. Another result I might teach in this vein is Feigenbaum-Fortnow (no worst-case to average-case reductions of a restricted type exist for NPC sets, unless the PH collapses via AM protocols). This result could tie you in to a course unit on foundations of cryptography and the attempt to base crypto on NP-completeness.
why can't PH collapse?
ReplyDeleteI think it's a good theorem for a non-theorist to prove. It is in a way a programming task: design a poly algorithm for SAT that makes use of a sparse NPC problem.
ReplyDeleteThe modern complexity book draft features mahaney's theorem as an exercise.
why can't PH collapse?
ReplyDeleteIt would be surprising for the same reasons that P=NP would be surprising -- a collapse would imply that eventually P=NP relative to, say, \sigma_{42}. \exists X \forall Y \exists Z... might be hard, but eventually adding a few extra quantifiers doesn't make the question much harder.
That said, I wouldn't be fundamentally shocked if it did, though I would be quite surprised.
Why teach Mahaney's theorem to non-theorists?
ReplyDeleteFirst, why teach Fortune's theorem? Because it contains an interesting algorithmic core, and illustrates how an equivalence relationship can be used to in an interesting computational way.
Second, why teach Mahaney's theorem? Because it uses Fortune's theorem in an algorithmically interesting way. It is a surprising application of the general principle of guess and check.
So I would argue that, for non-theoretician's, there's not much meat in Fortune's and Mahaney's theorems, but there is a lot of good meat in their proofs.
You mentioned doing the Berman-Hartmanis paper as a stepping stone to Mahaney's theorem, as though you weren't already doing BH in the class.
ReplyDeleteBut I think, perhaps more than Mahaney, BH should be taught to a class of non-theorists. The fact that all known NPC sets are isomorphic -- essentially just re-encodings of the exact same set -- is really interesting, regardless of the ultimate status of the isomorphism conjecture. Even more so when you consider what things we know are NPC: knot genus, quadratic diophantine equations, sudoku, optimization problems are some big ones that may resonate with a non-TCS crowd. But they're all in fact the exact same problem: not just polynomially reducible to one another, but the *same* problem! (Non-theorists, eat your hearts out.)