Timeline for Proving P = NP without mathematical statements / computer program
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23, 2013 at 18:41 | history | edited | Thomas Klimpel | CC BY-SA 3.0 |
copied interesting references and justifications from the comments into the answer itself
|
| Aug 18, 2013 at 19:36 | comment | added | Thomas Klimpel | Scott is famous for trying to demonstrate what it means that he "knows" something, for example by betting $200,000: scottaaronson.com/blog/?p=458 | |
| Jan 17, 2013 at 0:13 | comment | added | Thomas Klimpel | A long time ago, Scott Aaronson wrote this comment: " anonymous: You claim (as being fact!) that 3SAT is a language in NP that cannot be computed in polynomial time. But you cannot prove it. Is that your scientific method? Yes. As a firm believer in science and reason, I strive to distinguish clearly between what I can prove and what I merely know is true. " | |
| Jan 15, 2013 at 7:24 | comment | added | Raphael | @ThomasKlimpel There are many techniques for proving that a formal language is not regular (or context-free, or decidable, or...), but still there are plenty of them. | |
| Jan 15, 2013 at 1:15 | comment | added | Thomas Klimpel | @Raphael Your statement "In the case of P≠NP, the only evidence we have is a lack of evidence" seems even more bold than my statement "of course P != NP, the question is just how to prove it". In his 1971 paper, Stephen Cook still had to admit that he was unable to produce counterexamples for the Davis-Putnam procedure (solved by Haken 1985). Today, many techniques, results and counterexamples are available for "disproving" proposed efficient NP-solvers. Also P = NP contradicts the "law of conservation of difficulty", the "qualitative infinitary <-> quantitative finitary" correspondence, ... | |
| Jan 15, 2013 at 0:30 | comment | added | Thomas Klimpel | @NieldeBeaudrap The comment was posted here. I was inquiring whether you are aware that Gödel contributed more than just his Incompleteness Theorem. The unspeakable "of course P != NP, the question is just how to prove it" is a reply to your comment that "if P versus NP were independent of ZFC, wouldn't this suggest that there are no polytime algorithms for NP". The point about this answer is that if I decide to state the "unspeakable", I can as well do it openly as an answer (to an appropriate question). This also allows for feedback... | |
| Jan 14, 2013 at 14:25 | comment | added | Raphael | @ThomasKlimpel In other sciences, we'd have observations to back up the hypothesis. In the case of P$\neq$NP, the only evidence we have is a lack of evidence (namely the fact that nobody has been able to come up with a polynomial-time algorithm for an NP-hard problem). I don't think other sciences would use a lack of observation as means to "prove" something; if you have never seen an apple detach from its tree, how can you claim it would (not) fall? | |
| Jan 14, 2013 at 13:17 | comment | added | Niel de Beaudrap | @ThomasKlimpel: I remember posting that comment, but not where. Given that whomever I was responding to (you?) was simply using him as an authority to argue for the correctness of mathematical Platonism, whereas I have after some consideration arrived at a formalist position, the mere fact that Godel had a different opinion without further elaboration is indeed irrelevant. Technical arguments are not won as tennis matches are, with a swift rebuttal. Similarly, convincing answers are judged not solely by their concision (though that helps) nor by authority, but by their technical merit. | |
| Jan 14, 2013 at 8:34 | history | edited | Thomas Klimpel | CC BY-SA 3.0 |
focus answer on the main point
|
| Jan 5, 2013 at 17:53 | comment | added | Thomas Klimpel | I want to point out an irony with respect to "know ... for all practical purposes", "mathematical proof" and the relation between Gödel's incompleteness theorem and P vs NP. As Gödel himself wrote to von Neumann, if P=NP were true "for all practical purposes", then his incompleteness theorem would only be true in theory, but effectively false in practice. Conclusion: Even if we prove a theorem which formalizes some fact which we "know is true for all practical purposes", this normally doesn't establish the truth of our empirical knowledge beyond all doubt. The burden of proof is too heavy. | |
| Jan 5, 2013 at 17:40 | comment | added | Thomas Klimpel | @PeterShor After reading a book of Palle Yourgrau about Kurt Gödel and observing how "Niel de Beaudrap"'s position with respect to the relevance of Gödel's work and philosophical position ("Gödel and I have irreconcilable differences in philosophy of mathematics, so his opinions ... irrelevant") exactly matched Yourgrau's observations, I decided to explicitly state the "unspeakable". This is also related to Gödel, who tried to publish only flawless papers and completely polished thoughts, but couldn't prevent by this that his thoughts and philosophical positions were dismissed as irrelevant. | |
| Jan 5, 2013 at 13:27 | comment | added | Peter Shor | In mathematics, the problem with ignoring proof and proceeding blindly forward is that you may assume something that is wrong. This will make the quest go much slower. The physical sciences don't have this problem (except for cases like quantum gravity/string theory) because they have to agree with experiment. | |
| Jan 4, 2013 at 10:15 | comment | added | Thomas Klimpel | @GeorgeB. From Proof vs. Truth in Computational Complexity: We could remain agnostic, saying that we simply don’t know, but there can be such a thing as too much skepticism in science. For example, Scott Aaronson once claimed [Aar10] that in other sciences P ≠ NP would by now have been declared a law of nature. I tend to agree. After all, we are trying to uncover the truth about the nature of computation and this quest won’t go any faster if we insist on discarding all evidence that is not in the form of mathematical proofs from first principles. | |
| Jan 4, 2013 at 3:03 | comment | added | George | Nobody "knows" that P != NP. Experts may strongly believe it, but no expert knows it (unless somebody has a proof and kept it for himself/herself). It is possible, although unlikely, that P = NP is true. As a side-note, everybody (especially scientists) should be open to everything, unless proven otherwise. In this case every scientist, however large his belief is that P != NP, should accept that there is the possibility that P = NP holds. | |
| Jan 4, 2013 at 2:34 | comment | added | Thomas Klimpel | @YuvalFilmus The amount of false proofs produced by amateurs has nearly no impact on the opinion of "elite professionals". However, there is the hope that showing an amateur the amount of existing false proofs might help to improve his perspective of where he currently stands. Also note that I'm serious when I refer to "know" in my answer. The fact that an expert "knows" some things just because of his experience even if he can't rigorously prove them is something surprisingly difficult to grasp for a non-expert. (And this doesn't just apply to unsolved problems, but also to effort estimation) | |
| Jan 4, 2013 at 1:11 | comment | added | Yuval Filmus | Amateurs have produced many proofs of P=NP as well as P$\neq$NP. For that reason, "elite professionals" are unlikely to seriously consider efforts by amateurs. However, if a proof is correct, it will be accepted by "elite professionals". The result might not be relevant to the real world practitioners (indeed, I think that is going to be the case), but "professional" theoretical computer scientists will care anyhow. | |
| Jan 4, 2013 at 0:59 | history | answered | Thomas Klimpel | CC BY-SA 3.0 |