At TTI yesterday, K. V. Subrahmanyam gave a talk giving one of the better overviews of Ketan Mulmuley's Geometric Complexity Theory approach to separating complexity classes. This approach reduces various problems including P ≠ NP to hard problems in algebraic geometry.
Afterwards at lunch, Ketan made it clear that he believes
- GCT will eventually lead to proving P versus NP. In fact, any proof that NP is different than P must go via GCT.
- Such a proof will not happen in my lifetime.
Ketan is not even giving me that opportunity. Consider a huge mountain and you want to reach the mountaintop. Ketan comes along and says he'll teach you how to create the tools needed to climb the mountain. It will take a hard month of study and actually these tools aren't good enough to climb the mountain. They need to be improved and these improvements won't happen in your lifetime. But don't you want to learn how others will climb the mountain centuries from now?
If you want to spend the month, go here and start reading. Let me know when you've been enlightened.
Been enlightened. Thanks!
ReplyDeletethis post is silly. you just don't believe the guy. I have to say that any self-respecting complexity theorist, if they *truly believed* that the resolution of P vs. NP must go through Mulmuley's program, would at least sit down and try to grasp it. the point is that you don't believe it, or maybe you do, but only in a superficial way.
ReplyDeletejust like the resolution of P vs. NP must go through protein folding (after all, it's an NP-complete program), but you don't rush off to learn biochemistry.
So - does Mulmuley's flips stand bypass Aaronson-Wigderson's Algebrization barrier?
ReplyDeleteWhat was his ground for claiming that a proof *must* go through GCT? If there is a correspondence of P vs NP with some problem in algebraic geometry, why would this direction be much more believable than saying that some problems in algebraic geometry may be solved through complexity theory counterparts?
ReplyDeleteConsider this a general question, if you will, about when problems in domain A "must" be solved through problems and tools of a different domain B.
This post is quite boring. The only problem with GCT
ReplyDeleteis that it will not help you getting "yet another paper
at STOC", or something similar (see posts like: "hey, we all have to play the game and write rubbish proofs to get the paper accepted"). Reading some of your posts it really seems as you are interested in your curricula and paperlist more than in Science. I know
this is not the case, so please write seriuos posts.
And go study algebraic geometry :)
Nonsense
ReplyDeleteI dont think it is the algebraic geometry or representation theory that is stopping people from understanding it.. if needed people can pick up the math..
ReplyDeleteOfcourse, one would be interested in the proof of P!=NP and not just the statement itself. If we were only interested in the statements rather than proofs, like physicists
we would made it a law long ago.
I think once anyone proves some complexity class separation using the approach, it will get people interested. As of now, with no other big class separation coming out of the approach, people find it hard to believe it is the way to solve NP=P.
There are many reasons not to climb mountains.
ReplyDeleteHowever, it is not too much to ask a person who "really cares about" climbing the mountain and is an expert on mountain climbing to try new equipment even if the goal remains out of the immediate reach.
Then again, many pretty hills are readily accessible for a pleasant day trip.
I would read it but it's in postscript and I can't get it to work on my Windows Vista machine. Sigh.
ReplyDeleteNumbers 2 and 5 are being assholes. (And probably trolls. I also think they're the same person. Watch how the first sentence is a blunt flame).
ReplyDeleteBut just for the record (and because I wrote the response before I realized that they're trolling) :
This post is one of the best I've read on this blog, especially Lance's explanation about why he isn't pursuing studying GCT and the direction of proving P!=NP through GCT. You can agree with it or disagree with it, but saying that it is "silly" or "boring" is plainly foolish.
Number 5 -- get off your high horse. You, of course, close yourself in your mountain hideaway, or live in your mother's house, and give yourself to science 24/7, in order to be the first to prove Goldbach's conjecture? Give me a break. Science needs a variety of researchers, going for a variety of goals. If you're such a good critic, write your stupid comments under your own name, and enclose your publication record, so that we can all see how you are so devoted to pure scientific thoughts, untouched by any thought of getting ahead in the academic track by (gasp) writing papers.
Oh, and number 2 -- go learn some computer science. there is no such thing "NP-complete program". There is a _program_ to prove P!=NP through GCT. Protein folding is an NP-hard problem, so you'll have to prove it's not poly-time solvable to prove P!=NP. Good luck. Tell number 5 when you prove it. I'm sure he'd love to know how devoted you are to science.
While it might be too early to say if "Geometric Complexity Theory" deserves to be called a "Theory" (in the sense that "Representation Theory" is a theory) -- it is very much within the realm of possibility that current research in computational complexity theory lacks the mathematical depth required to tackle a problem of the nature of P/NP. Algebraic geometry and representation theory might very well provide the mathematically deeper tools needed to make non-zero progress towards resolving this conjecture. This remains to be seen -- but if it does happen such a proof will probably not come from the theoretical CS community as defined by STOC/FOCS, but would probably originate from and be evaluated by mathematicians. In this respect Lance is probably right when he says he wouldn't be interested in the details of such a proof -- very few people in theoretical CS would I am guessing.
ReplyDeleteInteresting Column by Lance Fortnow: http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column78.pdf
ReplyDeleteA reasonable definition of an "NP-complete program" is one which runs in polynomial time (against a language in NP?) iff P=NP.
ReplyDeleteWhat was his ground for claiming that a proof *must* go through GCT?
ReplyDeleteNothing whatsoever. It's exceedingly difficult to justify such a claim, and I can't imagine how one could possibly justify it in advance. At best it's a highly biased personal intuition. He might be right - I'm sure his intuition on this problem is better than mine - but I wouldn't count on it.
For comparison, consider primality testing. Starting with Miller's work in the 70's, people got very good at giving short, simple, efficient primality tests that provably run in polynomial time, if certain high-powered number-theoretic conjectures (such as the Riemann hypothesis for Dirichlet L-functions) hold. It would have been reasonable to suspect that these sorts of conjectures were a necessary step on the way to getting a provably polynomial-time primality test, but of course they weren't.
I actually agree with commenter #2 (except that I wouldn't call Lance's post silly). Very few people really believe Mulmuley when he says this is the right approach to P vs. NP. Everybody acknowledges that he might be right, but I think the people who are truly convinced could be counted on one hand.
In this respect Lance is probably right when he says he wouldn't be interested in the details of such a proof -- very few people in theoretical CS would I am guessing.
That's kind of sad, if true, considering how central this problem is to computational complexity. If GCT works out, then I suspect a lot of interest in it will suddenly materialize. If not, then I suspect the field will get taken over by people with more background in algebraic geometry. (This is of course assuming it is the right approach to P vs. NP, which I'm skeptical about.)
Something similar happened in algebraic geometry itself in the 50's and 60's. There's a famous book review by Mordell of Lang's Diophantine geometry book, in which he complained quite bitterly that he couldn't understand the abstract machinery the younger generation was using and didn't really think it was necessary. In fact, he described things in fairly insulting terms (Lang was a pig rooting about in the garden of classical algebraic geometry).
Mordell was 100% wrong, and nowadays everybody in the field uses highly abstract machinery without complaint. I don't expect this will happen to computational complexity theory, but in principle it could happen. Then some of the complexity theorists of the 90's would end up writing bitter reviews of books that use homological algebra to prove that the polynomial-time hierarchy doesn't collapse...
please give me an example of any big problem in mathematics that was solved using a connection to a completely different branch, where the connection itself couldn't be understood through the lens of much simpler phenomena, e.g. reproving some old easier results in the initial field first. I don't know of cases where there is a connection, but understanding *why* can't be given with some very simple examples (e.g. diff eq in Perelman's proof or elliptic curves in FLT).
ReplyDeleteMulmuley's stuff looks like smoke and mirrors. and it's poorly written on top of that.
look at Joel Friedman's "Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity." it's like people don't realize that math was built from the ground up, and you just don't invent huge abstract objects hoping that significant connections will fall out.
Would the complexity of an algebraic geometry proof of P!=NP constitute the proof? You probably need one or more "transcendental" theorems linking Complexity and some particular field in math. There actually are math theorems that bridge large swathes of algebra and analysis as well as algebraic geometry which clearly is itself a "transcendental" bridge of algebra and geometry. (By transcendental I don't mean involving e and pi, or Kantian philosophy, but involving an overarching viewpoint not obviously derived from either.)
ReplyDelete"Also while knowing the resolution of P v. NP is very important, knowing the details of the proof, especially if it requires deep and complex mathematics, is not nearly as important."
ReplyDeleteIt's surprising that you feel this way. Presumably this only applies to the case that P not equal to NP, but even in the other case it's surprising.
It would make a pretty boring complexity text book to have a sequence of results with no proofs. The thing that is most exciting to me about results like parity not in AC0 is not the result themselves, but how you could possibly prove something like that.
I also feel that this applies not just to complexity theorists but also to regular folk.. tell someone that there is no efficient way to solve TSP and they usually want to know how you could possibly know that.
Conditioned on believing that P is not equal to NP, knowing its truth seems to add very little. Everything that's interesting is in the proof...
-anup
I wonder if Anon 7 and Anon 15 are aware of Ketan's lower bounds for the PRAM model without bit operations. These lower bounds use some of the GIT machinery. Given that we have no lower bounds for any class bigger than AC^0[p], this is a very interesting result, and I'm surprised it's not better known...
ReplyDeleteThe problem is that Ketan is uncomfortable proselytising.
A tangent, but one I think is relevant: what about the work of Herlihy (and others) using algebraic topology to prove results in asynchronous computing? These seem to me to be very interesting results (they won the Godel prize), yet the techniques don't seem to have been picked up widely by anyone else, in part because they still don't seem very well understood. (As an aside, the original papers appear to be unreadable, and I am not aware of any better account of the results -- perhaps this is part of the problem.)
ReplyDeleteTo Anon 19: In fact there is a lot of work being done by people working in the general area of model categories (axiomatic homotopy theory) who are applying ideas from homotopy theory to study problems in concurrency. See for instance the work of Peter Bubenik and others. The initial work in distributed computing by Herlihy et al. is very elementary from this point of view.
ReplyDeleteBut as in the case GCT the run-of-the-mill theoretical computer scientist (with his/her STOC/FOCS deadlines, not to mention SODA/WINE/BEER etc.) most likely will not want to devote a year needed to learn the necessary background (the theory of model categories as started by Quillen) to follow this work. I guess the same is true with respect to Representation Theory in case of GCT (which probably would need a couple of years).
There are more than a few people in the FOCS/STOC community who have absorbed enough representation theory to work seriously on the Hidden Subgroup Problem in quantum computing. Given how hard HSP is proving to be, you would think that if the GCT approach to P vs NP were appealing they would be enticed to switch what they are working on to make use of their efforts. Somehow that hasn't happened.
ReplyDeleteI think that the reason Ketan says that
ReplyDeleteGCT is likely to be how P != NP will be proved is that there is little "information loss" [KVs words] in his concise geometric reformulation. An alternate route to proving P != NP would also end up proving a theorem about "the representation theory of the permanent and determinant varieties". Though certainly possible, it seems unlikely that something like this could be achieved by an argument having no geometric/ representation theoretic component whatsoever.
I agree with Anup. We are in this business for the proofs and reasons why certain phenomena are correct, not for the facts themselves.
ReplyDeleteAlso while knowing the resolution of P v. NP is very important, knowing the details of the proof, especially if it requires deep and complex mathematics, is not nearly as important.
ReplyDeleteSince P v. NP is basically the central question in complexity theory, it's pretty important for complexity theorists to have at least a high-level understanding of the proof. This is true for the same reasons number theorists should at least understand the outline of Wiles' proof of FLT, or extremal combinatorialists should know the general overview of the proof of Szemeredi's regularity lemma, without necessarily seeing the fine details -- the tools used in the proof can probably be adapted to attack other problems, which is our job.
If Mulmuley's program were better-defined, if it were (say) analogous to Hamilton's program for proving Thurston's geometrization conjecture, then it'd be worth it for complexity theorists to learn some algebraic geometry and representation theory. And if Mulmuley or someone else were to carry through this program and prove P != NP, then complexity theorists would almost have to learn enough to understand the basic scheme of the proof. But I agree with what I think Lance is trying to say here, in that trying to discover the details of a "proof" a priori is silly.
GCT is likely to be how P != NP will be proved is that there is little "information loss" [KVs words] in his concise geometric reformulation. An alternate route to proving P != NP would also end up proving a theorem about "the representation theory of the permanent and determinant varieties". Though certainly possible, it seems unlikely that something like this could be achieved by an argument having no geometric/ representation theoretic component whatsoever.
ReplyDeleteAgain, this is silly. On the one hand, it's the nature of P vs. NP and the startling success of NP-completeness; you can basically encode the P vs. NP *losslessly* in any field that you want. I disagree that it would be surprising for the argument to have no geometric/representation theoretic component. The truth is that once you construct something very complicated, and concentrate on the algebraic structure within that *specific* object (instead of arguing about a general class of objects), you move away from the domain of algebraic geometry.
``The truth is that once you construct something very complicated, and concentrate on the algebraic structure within that *specific* object (instead of arguing about a general class of objects), you move away from the domain of algebraic geometry.
ReplyDelete"
In principle any algebro-geometric argument can be deconstructed until it is ``pure combinatorics" or even further down to the axioms of set theory. However in the process the proof might blow-up and be humanly unreadable. The question is then whether algebraic geometry/representation theory is a useful descriptive language as a first step for a proof of P != NP. There is a case that can be made in Ketan's favor, given that he and Sohoni have shown relations to positivity conjectures belonging to mainstream representation theory.
This comment has been removed by the author.
ReplyDeleteIn principle any algebro-geometric argument can be deconstructed until it is ``pure combinatorics" or even further down to the axioms of set theory. However in the process the proof might blow-up and be humanly unreadable.
ReplyDeleteThe FPRAS for the permanent of 0/1 matrices seems very natural in the combinatorial setting, even if it concerns an algebraic object.
(Nitpick) James, algebraists often say that the permanent is not really an algebraic object. it is not invariant under change of basis.
ReplyDeleteKetan Mulmuley=Vinay Deolalikar
ReplyDeleteAnon30 = Coward.
ReplyDelete