tag:blogger.com,1999:blog-3722233.post7062479950089498370..comments2021-12-01T13:41:42.544-06:00Comments on Computational Complexity: Should Mahaney's theorem be taught in a complexity grad course for non-theorists?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-60844931908084561482008-04-30T20:34:00.000-05:002008-04-30T20:34:00.000-05:00You mentioned doing the Berman-Hartmanis paper as ...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.<BR/><BR/>But 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.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4902564786180582692008-04-30T13:46:00.000-05:002008-04-30T13:46:00.000-05:00Why teach Mahaney's theorem to non-theorists?First...Why teach Mahaney's theorem to non-theorists?<BR/><BR/>First, 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.<BR/><BR/>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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70163380739501812442008-04-30T07:37:00.000-05:002008-04-30T07:37:00.000-05:00why can't PH collapse?It would be surprising for t...<I>why can't PH collapse?</I><BR/><BR/>It 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.<BR/><BR/>That said, I wouldn't be fundamentally shocked if it did, though I would be quite surprised.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39681239462012523942008-04-29T20:25:00.000-05:002008-04-29T20:25:00.000-05:00I think it's a good theorem for a non-theorist to ...I 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.<BR/><BR/>The modern complexity book draft features mahaney's theorem as an exercise.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38542787244612631652008-04-29T19:41:00.000-05:002008-04-29T19:41:00.000-05:00why can't PH collapse?why can't PH collapse?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80248262550818366272008-04-29T13:31:00.000-05:002008-04-29T13:31:00.000-05:00I think the general project of showing that unlike...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).<BR/><BR/>What 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.<BR/><BR/>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.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7219275712746362532008-04-29T12:19:00.000-05:002008-04-29T12:19:00.000-05:00Here's some old-school intuition: since we believe...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.<BR/><BR/>I'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.)ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.com