[Computational Complexity] Should Mahaney's theorem be taught in a complexity...
- Today we discuss another theorem in terms of should it be taught in a basic complexity course (taken mostly by non-theorists) (There was an earlier blog about this for PARITY ¬in AC0.)
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.)
Posted By GASARCH to Computational Complexity at 4/29/2008 11:31:00 AM