tag:blogger.com,1999:blog-3722233.post7235975830092653095..comments2020-02-19T03:43:18.369-05:00Comments on Computational Complexity: QIP = PSPACELance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1407936934010384642009-07-30T12:16:44.315-04:002009-07-30T12:16:44.315-04:00"every separation is a collapse in disguise&q..."every separation is a collapse in disguise"Teutschhttps://www.blogger.com/profile/04848264673734802964noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36950000087966050312009-07-29T23:08:50.509-04:002009-07-29T23:08:50.509-04:00It seems unlikely that this'll have the same e...It seems unlikely that this'll have the same effect that IP = PSPACE did; for one thing, the "hard" collapse for the quantum case is the "easy" part classically. Still a great result.<br /><br />My question, though -- will this have an effect on the study of QMA, and in particular will we finally be able to formulate the "right" quantum analogues of various classical results around P and NP? (I'm thinking in particular of stuff like Valiant-Vazirani, the PCP theorem, etc, which as far as I know don't have good quantum counterparts.)harrisonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5602509323548525512009-07-29T18:48:23.227-04:002009-07-29T18:48:23.227-04:00Probably the nicest way to summarize all this is ...Probably the nicest way to summarize all this is QIP = BQPSPACE = PSPACE = IP (the middle equality was proved by Watrous 11 years ago). If we only knew whether or not BQP was in the PH...Jonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25720568633499600242009-07-29T14:34:29.423-04:002009-07-29T14:34:29.423-04:00"But I can't help observing the irony: co..."But I can't help observing the irony: complexity is a field that's supposed to be doing lower bounds and separations, but almost all great results have been upper bounds and class collapses :)"<br /><br />A "collapse" says that we have found yet another definition for the same thing. This is always good--to look at the same thing from different sides. But I share your "irony:" in circuits complexity we have just an opposite. There most of "classes" (=restricted circuit models) turn out to be *incomparable* in their power (=do not collapse). Why? I think because the reason to introduce these classes is different: they localize the scope of a particular lower bounds argument.The "importance" of the resulting model is secondary. The goal is to prove *any* nontrivial lower or surprising upper bound, not just to find a new definition. I think this is where the "high level" and the "low level" complexity differ. <br /><br />Randomness is good, quantum is even more attractive. But what about the "classics", about what we have and will have for a long time? Do we really hope to understand the power of quantum algorithms without having understood that of "simplest", classical ones? This nice result just shows that we *cannot* hope.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56249663578428393392009-07-29T11:29:39.660-04:002009-07-29T11:29:39.660-04:00Complexity in supposed to determine how difficult ...<i>Complexity in supposed to determine how difficult computations are. This may involve nontrivial upper bounds, or nontrivial lower bounds.</i><br><br /><br />I guess that would be called "Theoretical Computer Science". The separation between algorithms and complexity is of course hard to draw formally (a formal separation shouldn't exist!), but it's hard to argue that the classes Algorithms, Complexity, and TCS collapse.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41387259141533012942009-07-29T11:04:41.576-04:002009-07-29T11:04:41.576-04:00The idea that "we are supposed to be doing lo...The idea that "we are supposed to be doing lower bounds and separations" is not correct.<br />Complexity in supposed to determine how difficult computations are. This may involve nontrivial upper bounds, or nontrivial lower bounds.<br /><br />Upper bounds are easier: you have to prove existence of something. For a lower bound you have to prove nonexistence. Not surprisingly, we have been more successful in the former than the latter.<br /><br /><br />As for making up problems,<br />coNL was not a "class invented to collapse". Similarly, in IP=PSPACE if one wants a class we "invented" it would be IP, and it is not hard to prove that IP is contained in PSPACE. The unexpected collapse is that IP can simulate PSPACE.<br /><br />It is true that we made little progress in fundamental lower bounds. The reasone may be that these problems are truly very difficult. Moreover, at least some (e.g. Mulmuley) believe that in fact the difficulty in ALL these problems is the same, and major mathematical obstacles have to be overcome in order to make progress.CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66456574511969740102009-07-29T10:33:11.220-04:002009-07-29T10:33:11.220-04:00This is definitely a great result. But I can't...This is definitely a great result. But I can't help observing the irony: complexity is a field that's supposed to be doing lower bounds and separations, but almost all great results have been upper bounds and class collapses :) [Say, IP=PSPACE, Toda, NL=coNL, PCPs for NP, derandomization...]<br /><br />How do we fight the following criticism (which is unreasonable, but not totally so): we are inept at doing what we're supposed to be doing, so we keep inventing problems we can solve (classes that might collapse), and anointing them as important.Anonymousnoreply@blogger.com