tag:blogger.com,1999:blog-3722233.post174819339704705868..comments2023-02-04T09:02:15.330-06:00Comments on Computational Complexity: Don't Have an End GameLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-3722233.post-26196567179167358652013-08-13T01:35:13.203-05:002013-08-13T01:35:13.203-05:00Grigori Jakowlewitsch Perelman believes he can con...Grigori Jakowlewitsch Perelman believes he can control the universe, not only TCS.<br /><br />best,<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22636289913346765512013-08-12T22:11:54.129-05:002013-08-12T22:11:54.129-05:00wow, haven't seen this guy post his claims in ...wow, haven't seen this guy post his claims in a while, like almost three years I thinkAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75372668765090679142013-08-12T14:22:53.843-05:002013-08-12T14:22:53.843-05:00Q.E.D. ...
I forgot to add to (1) "and + 1 m...Q.E.D. ...<br /><br />I forgot to add to (1) "and + 1 mln price" ... will we have Grigori Jakowlewitsch Perelman in TCS?stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27285624038225808742013-08-12T06:40:29.745-05:002013-08-12T06:40:29.745-05:00By the vigor of their ideals, by the stability of ...By the vigor of their ideals, by the stability of their perceptions. By the vigor of their concepts, by the resoluteness of their outlooks.<br /><br />Best,<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15188577918705157862013-08-12T03:47:16.183-05:002013-08-12T03:47:16.183-05:00Unfortunately P vs NP has finally been resolved:&q...Unfortunately P vs NP has finally been resolved:"P=NP iff P!=NP". If you don't believe it, just ask Luca Trevisan and Boaz Barak about my recent (third) JACM submission.<br /><br />Best,<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88696825780654745772013-08-11T18:19:54.398-05:002013-08-11T18:19:54.398-05:00As Daniel Barrett once wrote, "If you said P ...As Daniel Barrett once wrote, "If you said P is NP tonight, there would still be papers left to write..."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26803472243067325372013-08-11T12:30:50.914-05:002013-08-11T12:30:50.914-05:00Actually, Lance is right when saying that "Ha...Actually, Lance is right when saying that "Having an ultimate goal can be very motivating but quite limiting if that goal is actually reached." As some dangerous consequences of having an "ultimate goal" I see:<br /><br />(1) The problem P=NP sounds something like Einstein's E=MC^2, very attractive.<br /><br />(2) Lots of "proofs/disproofs" -- a consequence of (1) -- which does not contribute to our field being accepted by others as a serious enough one.<br /><br />(3) Huge lack of motivation for young people to attack "less ambitious" problems, (to prove ANY non-trivial lower bound, in ANY non-trivial model) -- the most annoying consequence.<br /><br />(4) After P!=NP will be finally proved, the authorities (like NSF) can be indeed "convinced" that that's was with Comp. Complexity ...<br /><br />This is why -- especially because of (3) -- I am rather reserved with stating "ultimate goals". We could perhaps state them as "most urgent" or "most annoying" or "methodological" goals. Micro-world is not less complex than the universe. stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27109703061709903742013-08-11T06:56:31.880-05:002013-08-11T06:56:31.880-05:00As a mathematical problem, the resolution of P vs....As a mathematical problem, the resolution of P vs. NP would most certainly be a part of a developed and quite deep mathematical theory. As such, it would indeed not be the end of "complexity theory", as it would be a starting point of a new, further developed, mathematical theory. (Somewhat, like the resolution of continuum hypothesis is far from being the end of set theory.) <br />On the other hand, as Noam states, when viewing P vs. NP as a question about the nature of efficient computation, the resolution of P vs. NP could probably be the ending of a the theory of computational complexity.<br />Since I think of ToC as mathematics, I subscribe to the first viewpoint. ToC researchernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46789749741132385692013-08-11T06:11:49.468-05:002013-08-11T06:11:49.468-05:001) Gee, we don't even know the asy complexity ...1) Gee, we don't even know the asy complexity of mult and<br />thats been open since the Rhind pap. (1650 BC).<br /><br />2) While I am sure that Lance and most people would be delighted<br />if P vs NP is solved there may be some sort of let down.<br />I know a prof who told me that the day he GOT Tenure was sad<br />since after all of that effort the question finally becomes<br />OKAY, NOW WHAT? I am happy to say that prof DID answer that question<br />and has done well, but there is that moment when you pause to think<br />about it.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52015008042353410522013-08-11T06:11:41.317-05:002013-08-11T06:11:41.317-05:001) Gee, we don't even know the asy complexity ...1) Gee, we don't even know the asy complexity of mult and<br />thats been open since the Rhind pap. (1650 BC).<br /><br />2) While I am sure that Lance and most people would be delighted<br />if P vs NP is solved there may be some sort of let down.<br />I know a prof who told me that the day he GOT Tenure was sad<br />since after all of that effort the question finally becomes<br />OKAY, NOW WHAT? I am happy to say that prof DID answer that question<br />and has done well, but there is that moment when you pause to think<br />about it.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65181660212695231882013-08-11T03:24:45.820-05:002013-08-11T03:24:45.820-05:00What are "related" complexity questions:...What are "related" complexity questions: NP vs coNP? P vs NC? Solvability of natural problems in quasilinear time? <br /><br />The P vs NP question is the biggest prize out there but it would be surprising if the techniques that solve it automatically translate to every important complexity problem. More likely, as Russell suggests, it opens up many more directions to explore.Paul Beamehttp://www.cs.washington.edu/people/faculty/beame/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4849689558728158432013-08-11T01:28:40.898-05:002013-08-11T01:28:40.898-05:00Solving P vs NP will not be the end for computer c...Solving P vs NP will not be the end for computer complexity, it will be a new start. Actually I think the P=NP magical automatically solving everything algorithm is some kind of fantasm, a myth. The solution of N=NP may, more realistically, comes in the form of 1 or 2 new fundamental number theory theorems implying new maths reasoning possibilities, opening doors we don't even know about. <br />A new vision where computer complexity specialists and all the maths community will desperately be needed to solve all NP problems one by one using hours of our brains. I don't believe in magic, at all.Anonymoushttps://www.blogger.com/profile/12005749767583527357noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89185155126816097702013-08-10T21:38:23.888-05:002013-08-10T21:38:23.888-05:00I think that when Lance says "solve P vs NP&q...I think that when Lance says "solve P vs NP", he means also "and related complexity questions". I would take this to include both uniform and non-uniform complexity, both average case and worst case, both deterministic and randomized (and quantum), both time and space (and parallel time) and do all of the above with reasonably close explicit lower bounds and upper bounds. Many of us expect all of these to follow from whatever techniques suffice to solve the narrow definition P and NP, but if that is not the case, then clearly we want the wide definition rather than the narrow one.<br /><br />I for one would be quite happy if P vs NP (in the wide definition) was solved and the whole field is 'finished'. This is a 'happy end', and scientific fields often have 'ends' and then science moves to other open questions.noamnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74805478298372142602013-08-10T16:15:39.455-05:002013-08-10T16:15:39.455-05:00Whoa! So expecting such statements from a leading...Whoa! So expecting such statements from a leading tcs researcher is also an NP problem? We do live in a non-determinant universe, do we not? And even rule bound complexity theory is in that non-determinant universe. If we lived in a determinant universe then we would be able to reliably expect such statements. As I've suggested before, at the risk of sounding recursive, solving the P=NP problem is probably an NP problem. You would expect that in a non-determinant universe. Of course I'm not implying that it cannot be solved.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60325088519644838262013-08-10T15:57:23.284-05:002013-08-10T15:57:23.284-05:00I am completely with Russell Impagliazzo: P vs. NP...I am completely with Russell Impagliazzo: P vs. NP is just ONE of the things to be done. Neither of the two answers will "close" the field. The P-NP question is good to motivate the research for "foreigners" (NSF and others). But I often wonder why we put this P-NP question also as our "real flag". None of the (two) answers to this question will answer MAIN questions like "is multiplication harder than addition?", "does matrix multiplication indeed requires more than n^2 operations?", etc. Even if P=NP, we can have a growth from n to n^{billion} when going from NP to P. Neither Shannon, nor Kolmogorov, nor Lupanov would be happy when seeing this "advertised complexity theory", sorry Lance ... stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30972013972916638522013-08-10T07:01:48.402-05:002013-08-10T07:01:48.402-05:00Nice comment. And to be honest, i would not have e...Nice comment. And to be honest, i would not have expected such a statement from a leading tcs researcher...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48244142405308279362013-08-09T23:05:38.039-05:002013-08-09T23:05:38.039-05:00"Luckily for us the P versus NP problem is a ..."Luckily for us the P versus NP problem is a goal which will not likely be reached for a very long time."<br /><br />I would become very happen if somebody settled P-vs-NP, the Riemann hypothesis, etc. Wouldn't you?<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36588008258748737592013-08-09T21:06:29.345-05:002013-08-09T21:06:29.345-05:00Craig Venter sounds an practical note regarding co...Craig Venter sounds an practical note regarding complexity-related end-game objectives in this recent <i>Business Week</i> interview <b><a href="http://www.businessweek.com/articles/2013-08-08/craig-venter-on-the-hail-mary-genome-and-synthetic-meat" rel="nofollow">Craig Venter on the Hail Mary Genome</a></b>:<br /><br />----------------<br /><b>Q</b> <i>Can you explain what the Hail Mary genome is and where we are with it?</i><br /><br /><b>A</b> "It’s funny that that term got out there. We’re trying to design a basic life form—the minimal criteria for life. It’s very hard to do it because roughly 10 percent of the genes are of completely unknown function. All we know is if we take them out of the cell, the cell dies. So we’re dealing with the limitations of biology. If we start with this minimal synthetic cell that we’re designing and building now, you could recapitulate all biology by adding components to that cell. In theory, we could eventually get to humans by adding enough components to that genome."<br /><br /><b>Q</b> <i>Last year you made it sound like it was about to happen.</i><br /><br /><b>A</b> "It’s what the whole history of this field has been. I have been sure we’re about to solve all the problems, and next year people will say, “Where is it?” We have not done it yet. If we had, I probably wouldn’t tell you. But I wouldn’t lie."<br />----------------<br /><br />So what is the irreducible (Kolmogorov?) complexity of a DNA-based living organism, given complete freedom in synthetic organism design? Venter promised that his research would deliver a concrete upper bound … but it has proven far harder than anticipated to deliver upon this promise.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15267609904717238382013-08-09T15:48:24.580-05:002013-08-09T15:48:24.580-05:00As we all know, Hilbert's great objective was ...As we all know, Hilbert's great objective was to provide provably complete and consistent axiomatic foundations to mathematics. And we all now appreciate that Hilbert's (seemingly reasonable) objective was unachievable.<br /><br />The lesson-learned is that a reasonable broader objective for 21st century complexity theory is to seek broader and more various foundations for it, within which issues associated to completeness and consistency can be assessed with greater confidence than in the 20th century.<br /><br />The past decade has witnessed a burgeoning of constructivist mathematical enterprises — <b><a href="http://homotopytypetheory.org/2013/06/20/the-hott-book/" rel="nofollow">HoTT</a></b> for example — that provide concrete frameworks for crafting broader foundations for 21st century complexity theory.<br /><br />After all, neither young nor old complexity theory researchers, nor the practical STEM enterprises that rely upon advances in complexity, are well advised to focus upon objectives that (in judgment of Lance and many eminent researchers) "will not likely be reached for a very long time" … objectives that (as Hilbert and Gödel teach us) may be out of reach forever.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44780794291186312212013-08-09T15:06:48.307-05:002013-08-09T15:06:48.307-05:00Bill --- Wiles's proof of FLT absolutely did s...Bill --- Wiles's proof of FLT absolutely did stimulate more research, notably, it led to the proof of the Taniyama–Shimura–Weil conjecture. It was an important development for the Langlands Program which is very much ongoing work. See http://en.wikipedia.org/wiki/Modularity_theorem<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83990768636007916772013-08-09T11:12:48.596-05:002013-08-09T11:12:48.596-05:00For Fermat's Last Theorem solving it did not b...For Fermat's Last Theorem solving it did not begin more research<br />(I don't think)<br /><br />For Szemeredi's theorem, solving it lead to more research.<br /><br />Godels Inc theorem lead to more research.<br /><br />The general question is- when a big open problem is solved does it<br />create a field or kill a field or both? Depends on the question.<br />One could look at all of Hilberts questions that were solved and see<br />if the solution created or killed (or whatnot) a field. (A good topic<br />for a blog--- but sounds too hard for me.)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65945437606978793032013-08-09T10:48:56.216-05:002013-08-09T10:48:56.216-05:00P neq NP is just the FIRST STEP in computational c...P neq NP is just the FIRST STEP in computational complexity. (If P=NP,<br />then we're in trouble.)<br /><br />Russell ImpagliazzoAnonymoushttps://www.blogger.com/profile/18394636887484222063noreply@blogger.com