Fields Medal Winner Terry Tao and others worked on Kakeya. There were partial results with difficult proofs. But the final proof was easy to understand. This does NOT mean it was easy to generate- we all suspect verifying is easier than generation. How easy was the proof to understand? So easy that I saw and understood a talk on it in seminar and was able to reconstruct it while proctoring an exam.
Whenever I see a math problem solved in a way that is easy but had been missed I wonder: is there an easy solution to P vs NP that is eluding us?
- Kakeya did not have a community of people working on it. Even though the people working on it were brilliant there were not that many of them. To solve a math problem may require a diversity of viewpoints. P vs NP has alot of people interested in it. Are they working on it? Do they have a diversity of viewpoints? I honestly don't know.
- There had been partial results on Kakeya. Hence there was hope. At this time there has been very little progress on P vs NP. (I would welcome counterarguments to this.)
- There were no results saying such-and-such technique cannot be used to solve Kakeya. For P vs NP there are several such results: oracles, natural proofs, algebraization. (hmmm- is having three results really having several results?). Is P vs NP the only currently open problem in math where there has been considerable effort in showing what techniques won't work? There may be some others in set theory where the conclusion Ind of ZFC is a real option, but how about in fields of math where we expect to get a real answer?
- If P=NP (which I doubt) then a simple-to-follow-but-quite-clever proof that eluded us all is plausible. If P\ne NP then I doubt this would happen.
Why do computer scientists believe that if P=NP, a short solution exists but if P/=/NP, then solution is likely long?
ReplyDeleteShouldn'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.
Because a polynomial algorithm to solve a single NP-complete problem will suffice to show that P=NP.
ReplyDeleteThe proof of correctness for the algorithm though could be very long.
ReplyDeleteInfact, 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).
ReplyDeleteIf 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.
ReplyDelete(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.")
There are many such stronger statements known for, for example, Riemann Hypothesis.
Bill Gasarch asks: Why can't we resolve P vs NP?
ReplyDeleteIn a recent blog post, 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 vice versa."
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."
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).
Here by "Golden Age" is meant Dirac's definition: "A Golden Age is an era in which ordinary people can make extraordinary contributions."
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. :)
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.
ReplyDeleteSidgalt -- 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.
ReplyDeleteTo 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.
To prove that P is not NP, you must show that an NP-complete problem cannot be solved by any 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.
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.
ReplyDeleteA 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.
ReplyDeleteIn 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".
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.
ReplyDeleteBeyond 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. :-)
Wikipedia page:
http://en.wikipedia.org/wiki/P-complete
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.
ReplyDeleteIf 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.
ReplyDeleteI 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.)
ReplyDeleteThere 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 ?
Anonymous says: 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.
ReplyDeleteWhat you say is true, but is it still true if we replace the phrase "difficult mathematics problems" by the phrase "important mathematical problems"?
Shannon's 1948-9 articles A mathematical theory of communication and Communication in the presence of noise are a well-known example of important mathematics results that were obtained by elementary (albeit ingenious) mathematics reasoning.
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: "The discussion is suggestive throughout, rather than mathematical, and it is not always clear that the author’s mathematical intentions are honorable."
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! :)
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.
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" ?
ReplyDeleteAny opinions or comments ?
>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" ?
ReplyDeleteAny opinions or comments ?
It is not the first, it will not be the last, nobody has time to waste reading papers by non-specialists.
take a look at here:
http://dblp.uni-trier.de/db/indices/a-tree/t/Tarnlund:Sten==Aring=ke.html
and here:
http://user.it.uu.se/~stenake/
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.
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.
There's a way out for those unknown folks who have little hope of convincing the community of the correctness of their proofs:
ReplyDeleteFormal computer checkable proofs!
These are proofs that we can write whose correctness can be checked by a computer program.
Some non-trivial proofs in mathematics already have computer checkable proofs!
See this article and the pointers in it for more information:
http://www.eurekalert.org/pub_releases/2008-11/ams-pbc110608.php
Of course the computer science community needs to do some ground work before such proofs become a reality in computer science
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.
ReplyDeleteJust to point out that there may be several DBLP entries for the same author. Here
ReplyDeleteis a candidate.
On the other hand, to me Corollary 6 in page 11 of that "P not NP" paper is incorrect.
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?
What will you say about www.timescube.com?
ReplyDeleteMy 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:
ReplyDeletehttp://jdh.hamkins.org/Publications
(at: P^f is not equal to NP^f for almost all f )
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
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.