tag:blogger.com,1999:blog-3722233.post5279655918396770124..comments2020-07-06T12:52:53.794-04:00Comments on Computational Complexity: The Kakeya Conjecture over finite fields resolved! Why can't we resolve P vs NP?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-3722233.post-31450767025422523472009-11-11T22:41:44.711-05:002009-11-11T22:41:44.711-05:00My knowledge of TCS is not very distinctive, so i&...My knowledge of TCS is not very distinctive, so i'm sorry if i write nonsense. However i think it's interesting that P vs Np seems to make sense and is even settled for infinite time turing machines at:<br /><br />http://jdh.hamkins.org/Publications<br /><br />(at: P^f is not equal to NP^f for almost all f )<br /><br />It would be exciting if one could make connections to the classical P vs NP Problem. For example if there would be an "infinite-time <br />Np-complete" problem U' very similar to a Np-complete problem U on a classical turing machine. By proving from U is in P follows U' is in P, P=!NP in infinite time would implie P=!NP on a classical turing machine. If i didn't get it complety wrong, i wonder whether such an attempt obviously relativizes.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20951545249448594072008-11-19T03:29:00.000-05:002008-11-19T03:29:00.000-05:00What will you say about www.timescube.com?What will you say about www.timescube.com?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37415452184194268752008-11-14T08:32:00.000-05:002008-11-14T08:32:00.000-05:00Just to point out that there may be several DBLP e...Just to point out that there may be several DBLP entries for the same author. <A HREF="http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/t/T=auml=rnlund:Sten==Aring=ke.html" REL="nofollow">Here</A><BR/> is a candidate.<BR/><BR/>On the other hand, to me Corollary 6 in page 11 of that "P not NP" paper is incorrect.<BR/><BR/>And, no, I am not trying to solve P versus NP, and I don't think I ever really was, even in the long gone days where I thought of myself as a complexity-theorist. And, in fact, now I suspect that really very few people is really trying. Should hope to be wrong?Balquihttps://www.blogger.com/profile/09857844891905542749noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83585144945628897612008-11-14T03:32:00.000-05:002008-11-14T03:32:00.000-05:00It is not that these papers claiming to resolve th...It is not that these papers claiming to resolve the P/NP question are by "non-specialist" authors. It is that they contain no new insights beyond arguments that have been thoroughly researched. It is unfortunately typical that these authors are also fundamentally unfamiliar with the notion of mathematical proof and when their fallacies are exposed are unwilling to withdraw their bogus arguments.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74819865946427489122008-11-14T00:42:00.000-05:002008-11-14T00:42:00.000-05:00There's a way out for those unknown folks who have...There's a way out for those unknown folks who have little hope of convincing the community of the correctness of their proofs:<BR/>Formal computer checkable proofs!<BR/>These are proofs that we can write whose correctness can be checked by a computer program.<BR/>Some non-trivial proofs in mathematics already have computer checkable proofs!<BR/>See this article and the pointers in it for more information:<BR/>http://www.eurekalert.org/pub_releases/2008-11/ams-pbc110608.php<BR/><BR/>Of course the computer science community needs to do some ground work before such proofs become a reality in computer scienceAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76584088946103076092008-11-13T23:02:00.000-05:002008-11-13T23:02:00.000-05:00>What about the following paper by Tarnlund at ...>What about the following paper by Tarnlund at arxiv.org/abs/0810.505 which claims to have settled the question to "P is not Equal to NP" ?<BR/>Any opinions or comments ?<BR/><BR/>It is not the first, it will not be the last, nobody has time to waste reading papers by non-specialists.<BR/>take a look at here:<BR/>http://dblp.uni-trier.de/db/indices/a-tree/t/Tarnlund:Sten==Aring=ke.html<BR/>and here:<BR/>http://user.it.uu.se/~stenake/<BR/>Does it really make sense that a person with one previous paper in 1981, which I don't know how much it is related to complexity theory, publishes his second paper proving P!=NP? Anyone proving P!=NP needs to show first what is the idea she/he uses which goes beyond negative results. That is all I can say.<BR/><BR/>ps. I do not mean an offense to anybody, and do not say that the proof is not correct, all I say is based on pragmatical consideration, people in complexity do not have time to read proofs of P!=NP by people outside it, unless they are convinced that the proof is correct, and one reasonable requirement is to see a one paragraph explanation why negative results do not apply to the proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14989301742314693132008-11-13T20:52:00.000-05:002008-11-13T20:52:00.000-05:00What about the following paper by Tarnlund at arxi...What about the following paper by Tarnlund at arxiv.org/abs/0810.505 which claims to have settled the question to "P is not Equal to NP" ? <BR/>Any opinions or comments ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61314102619364517062008-11-13T14:46:00.000-05:002008-11-13T14:46:00.000-05:00Anonymous says: I am sorry but the solutions of di...Anonymous says: <I>I am sorry but the solutions of difficult mathematics problems are (almost by definition) not simple -- and there is no short-cut to hard work.</I><BR/><BR/>What you say is true, but is it still true if we replace the phrase "difficult mathematics problems" by the phrase "<I>important</I> mathematical problems"?<BR/><BR/>Shannon's 1948-9 articles <I>A mathematical theory of communication</I> and <I>Communication in the presence of noise</I> are a well-known example of important mathematics results that were obtained by elementary (albeit ingenious) mathematics reasoning.<BR/><BR/>Yet back in the 1940s and 50s, not everyone regarded the simplicity of Shannon's articles as a virtue; for example Joseph Doob's (famously snarky) AMS review concludes: <I>"The discussion is suggestive throughout, rather than mathematical, and it is not always clear that the author’s mathematical intentions are honorable."</I><BR/><BR/>What I took to be the thrust of Garsarch's post is that P vs NP too might possibly be settled by some similarly simple yet unexpected line of reasoning ... if we're lucky ... and certainly it does not hurt to keep our eyes open! :)<BR/><BR/>You are absolutely right, needless to say, that there is no short-cut to hard work; Shannon's two articles were eight years in gestation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24385166342406700842008-11-13T10:06:00.000-05:002008-11-13T10:06:00.000-05:00I am sorry but the solutions of difficult mathemat...I am sorry but the solutions of difficult mathematics problems are (almost by definition) not simple -- and there is no short-cut to hard work. All credit to the the prover of the "finite field version" of the Kakeya conjecture -- but all that the short proof implies is that the finite field version does not capture the difficulty of the actual problem (which is considered a major open problem among harmonic analysts.)<BR/><BR/>There is an interesting analogy here with the P/NP problem here. The question of P/NP can be asked over any ring (admitting quantifier elimination) and Blum-Shub-Smale formalized this by defining real/complex Turing machines. As of now the problem is unresolved over any ring for which it makes sense. The original motivation of B-S-S, that complex algebraic geometry being better developed mathematically than other fields such as combinatorics in whose domain P/NP question has long being considered and is thus better suited to attack the problem, has not borne fruit, but who knows ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8920502390279149522008-11-13T00:06:00.000-05:002008-11-13T00:06:00.000-05:00If we find (not prove existence) to solve a NP-com...If we find (not prove existence) to solve a NP-complete problem, all we need to do is to use that program to find a proof of the theorem. If it has a feasible proof, the program will find it, and that is exactly why Godel said in his letter to von Neumann half a century ago that this is a very important problem. A more interesting consequence is we will have feasible programs working as mathematicians and solving open questions mathematicians tried to solve unsuccessfully in every field of mathematics. There are very good surveys on consequences of a constructive P=NP. So it seem completely reasonable that on one hand if we can find an algorithm for showing P=NP, and it has a feasible proof, we will find one, and the other hand, it is should be harder than any problem that we can solve in feasibly. So I, as many other do, predict that it is not correct, or at least it has no feasible constructive proof. This argument is in addition to other things like negative theoretical results stated above and our inability to find an algorithm to solve even one so many NP-complete problems in polytime. Please correct me if I am wrong.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5248128754843356032008-11-12T21:44:00.000-05:002008-11-12T21:44:00.000-05:00Andy, Sidgalt, "P-completeness" is usually used in...Andy, Sidgalt, "P-completeness" is usually used in the context of trying to separate L (or NC, or NL, etc) from P. The P-complete problems are the hard ones, just like NP-complete problems are the hard ones in the P vs NP question.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16626764667749290442008-11-12T21:36:00.000-05:002008-11-12T21:36:00.000-05:00To expand on what the anonymous commenter just sai...To expand on what the anonymous commenter just said, "complete" means "complete relative to a particular reduction," and you choose a particular reduction depending on what kind of computational hardness you want to compare. The Wikipedia page on P-Completeness discusses the relation between NC and P, essentially phrasing the question as, "Is every tractable problem inherently sequential?" That certainly seems like an interesting question to me.<BR/><BR/>Beyond that, if you use so-called first-order reductions, which is a reduction based on logical expressibility as opposed to space or time, you can get the result that the class P is precisely the class of languages over finite structures that can be expressed by first order logic with a least fixed-point operator. I find that very interesting... but I'm a logic dork, so maybe that doesn't count. :-)<BR/><BR/>Wikipedia page:<BR/>http://en.wikipedia.org/wiki/P-completeAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12575920026498749692008-11-12T21:27:00.000-05:002008-11-12T21:27:00.000-05:00A P-complete problem would be a problem which any ...<I>A P-complete problem would be a problem which any other problem in P reduces to in polynomial time. This means that virtually every decision problem in P (with some boring technical exceptions) is P-complete.</I><BR/><BR/>In sigdalt's use of it this is true but there is a full-fledged theory of P-completeness under NC (or log-space) reductions for which this statement is false. There is an entire book on the subject by Greenlaw, Hoover, Ruzzo entitled "Limits to Parellel Computation".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83257558393802617942008-11-12T21:05:00.000-05:002008-11-12T21:05:00.000-05:00There is a bit of man-bites-dog going on here. Tao...There is a bit of man-bites-dog going on here. Tao talks about this conjecture that was proved, not the thousands of other conjectures of equal interest and equal effort that remain open.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7904192501085363552008-11-12T20:32:00.000-05:002008-11-12T20:32:00.000-05:00Sidgalt -- A P-complete problem would be a problem...Sidgalt -- A P-complete problem would be a problem which any other problem in P reduces to in polynomial time. This means that virtually every decision problem in P (with some boring technical exceptions) is P-complete. This is why you aren't familiar with P-completeness -- it isn't interesting.<BR/><BR/>To show that P=NP, we would need to exhibit a polynomial time algorithm to solve, for example, SAT. Yes, in principle it could be difficult to prove that such an algorithm is correct, but unless its correctness is based on the zeroes of the Riemann Zeta function, I don't expect it to be that hard.<BR/><BR/>To prove that P is not NP, you must show that an NP-complete problem cannot be solved by <I>any</I> poly-time algorithm. A lot of things can happen in poly-time, and there seem to be very few proofs of any problem requiring super-polynomial time. In Bill's complexity course, the only proofs we had for "real" problems not being in P were based on those problems being EXPSPACE-complete -- suggesting they probably take more than exponential time. This might be analogous to proving that an NP-complete problem cannot be solved in constant time.Andy Parrishhttps://www.blogger.com/profile/12252029594014518238noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51756011408026784802008-11-12T20:23:00.000-05:002008-11-12T20:23:00.000-05:00According to Tao's weblog, the finite field versio...According to Tao's weblog, the finite field version of the conjecture didn't show up until 1999. That seems to break the comparison with P vs NP. Moreover, the real version is apparently still open.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19530928403737927882008-11-12T18:33:00.000-05:002008-11-12T18:33:00.000-05:00Bill Gasarch asks: Why can't we resolve P vs NP?In...Bill Gasarch asks: <I>Why can't we resolve P vs NP?</I><BR/><BR/>In a recent <A HREF="http://terrytao.wordpress.com/2007/03/18/why-global-regularity-for-navier-stokes-is-hard/" REL="nofollow">blog post</A>, Terry Tao memorably identified PDE research as "the type of mathematics where progress generally starts in the concrete and then flows to the abstract, rather than <I>vice versa</I>."<BR/><BR/>Perhaps P vs NP is similar? In the sense that—as Tao's blog observed of PDE research—progress may depend essentially upon some subtle feature of computational complexity that (in Tao's words) "is unlikely to be discovered abstractly before it is first discovered concretely."<BR/><BR/>It seems to me that nowadays, mathematicians, engineers, and scientists are together entering a "Golden Age" in which geometric, algebraic, and informatic approaches to complexity are joined (with quantum information theory accelerating this convergence, much as complex analysis accelerated functional analysis).<BR/><BR/>Here by "Golden Age" is meant Dirac's definition: "A Golden Age is an era in which ordinary people can make extraordinary contributions." <BR/><BR/>For this reason, I am cheerfully optimistic that substantial progress on P vs NP is coming, without having any definite opinion as to the form this progress may take. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1287214253518620532008-11-12T14:31:00.000-05:002008-11-12T14:31:00.000-05:00If you wanted to, you could look at counterexample...If you wanted to, you could look at counterexamples to stronger conjectures as "barriers" toward proving theorems -- any proof of theorem A has to not only be strong enough to prove theorem A, but it can't be so strong that it proves false statement B.<BR/><BR/>(Actually, you could look at oracles, etc., similarly: a stronger statement than P != NP would be P != NP respective to any oracle, but BGS shows this isn't true. There's another "stronger statement" that's disproven by Razborov-Rudich, but it's much more complicated.")<BR/><BR/>There are many such stronger statements known for, for example, Riemann Hypothesis.Johnhttps://www.blogger.com/profile/18079824074256670713noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34215374070511786392008-11-12T14:26:00.000-05:002008-11-12T14:26:00.000-05:00Infact, couldn't you turn the argument on its head...Infact, couldn't you turn the argument on its head because to show P/=/NP, all one needs to show is that an algorithm which solves a P-complete problem in polynomial time cannot solve an NP problem in polynomial time (since if P=NP, then every NP problem can be reduced to a P-complete problem in polynomial time)? (I am not very familiar with P-completeness so my understanding of that concept may be faulty).Unknownhttps://www.blogger.com/profile/08232757325795175217noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21947142779305048702008-11-12T14:14:00.000-05:002008-11-12T14:14:00.000-05:00The proof of correctness for the algorithm though ...The proof of correctness for the algorithm though could be very long.Unknownhttps://www.blogger.com/profile/08232757325795175217noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84666125311385828982008-11-12T13:39:00.000-05:002008-11-12T13:39:00.000-05:00Because a polynomial algorithm to solve a single N...Because a polynomial algorithm to solve a single NP-complete problem will suffice to show that P=NP.Kuroyamahttps://www.blogger.com/profile/05613785873616723639noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11043559274201279552008-11-12T11:40:00.000-05:002008-11-12T11:40:00.000-05:00Why do computer scientists believe that if P=NP, a...Why do computer scientists believe that if P=NP, a short solution exists but if P/=/NP, then solution is likely long?<BR/><BR/>Shouldn't it be exactly the other way around since any proof of P=NP would have to explain the abstraction(s) it used to prove that every NP problem can be solved by a polynomial time algorithm.Unknownhttps://www.blogger.com/profile/08232757325795175217noreply@blogger.com