4 ms·
P = NP
- pfortuny 13y agoI would wait until the paper has no more corrections made at least for a whole non-summer month. Well, it looks like there were no corrections in October but maybe he took his vacation then? Give it some more time, I suggest.
- robinhouston 13y agoIt’s fascinating how this sort of thing keeps attracting interest. Here’s a list of 100 proofs that P=NP or P≠NP, which includes this one: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://www.win.tue.nl/~gwoegi/P-versus-NP.htm There’s nothing to make this attempt more worthy of interest than the other 99, as far as I know.
- quchen 13y agoWhich makes me wonder: how do you filter these? In physics it's common practice to ignore papers about Perpetuum Mobiles (excuse the probably incorrect plural), but here we have a topic that is somewhat easy to write good and bad about while still having very high relevance.
- j2kun 13y agoHere's two lists of ways to filter. They're heuristics, but they work well. One for general mathematical proofs: http://www.scottaaronson.com/blog/?p=304 http://www.scottaaronson.com/blog/?p=304 One specific to P != NP: http://www.scottaaronson.com/blog/?p=458 http://www.scottaaronson.com/blog/?p=458
- Sniffnoy 13y agoTwo notes on these: 1. On the first one, note also numbers 11 and 12 Scott mentions in the comments. 2. The second is not always so specific to P vs. NP (and indeed has some overlap with the first -- #1 on the second list is a stricter version of #3 from the first). #3 and #4 for instance could be applied to lots of hard open problems, #6 to really any hard open problem, and #5 is basically fully general.
- DanWaterworth 13y agoCan anyone comment on how credible this is. It seems to have been submitted many times.
- this_user 13y agoEvery once in a while some publishes a paper that seeks to prove that N equals NP, but so far none were conclusive. Given that track record and the fact that the all existing evidence points to N unequal NP, I would be very cautious with this paper.
- jessaustin 13y agoI'm not going to dig into the paper, but I note that the abstract claims a constructive proof. I sort of assume that anyone with such a proof could organize a convincing demonstration by letting a disinterested observer provide a series of random numbers while clicking a stopwatch.
- petercooper 13y agoBut only when N is 1 or P is 0.
- skykooler 13y agoThis was already posted here. It is fatally flawed in that, although the theoretical computing time is polynomial, the memory required grows exponentially.
- topynate 13y agoI'm confident that the paper is indeed flawed. However, a Turing machine can neither write to nor read from an exponential number of locations in polynomial time, so the flaw will be something else.
- jmpe 13y agoMemory growth is not a consideration in the academic proof, Turing machine tape is infinite in both directions.
- taejo 13y agoTuring machines have may have infinite memory, but they can also only write one step per cell. So a polynomial-time TM can't use superpolynomial memory.
- deleted 13y ago[deleted]
- jessaustin 13y agoIn addition to what siblings said, remember that P is a subset of PSPACE.
- Gurkenglas 13y agoI think the statement you meant to remind us of is that NP is a subset of PSPACE.
- jessaustin 13y agoAccording to the paper under discussion, the two statements are equivalent. Your version is probably more graceful, however.
- jnazario 13y agoseems like a solid argument to me for peer reviewed publications.
- mion 13y agoThe best intuition I've read that P = NP can't possibly turn out to be true, is that if it were, you could write a piece of music as easily as you could appreciate it. Also, I can't imagine the answer to something as fundamental as this coming out of a hacky solution. There's probably a more elegant, natural way to prove it. And by natural I mean maybe they should start looking outside Turing's theory.
- Trufa 13y agoThat is a brilliant way of putting it, thanks!
- hansbo 13y agoI've read that one too, but I don't particularly like it. P=NP implies only that all problems which can be verified in polynomial time can also be solved in polynomial time, not necessarily that it can be solved as quickly, nor that it can be solved easily. Perhaps writing a piece of music is also done in polynomial time, but it requires more training (more advanced algorithm)? Or, perhaps, the time complexity is x^3 for writing, instead of x for appreciating.
- mion 13y agoAgreed, it is bit sensationalist. But what if someone proves it and then we realize that even though it can be done in polynomial time, there's some other constraint (like "x^N but N has to be super big") that renders the result impractical? I think once someone proves it, it will be obvious in hindsight as a lot of people are just ignoring the isomorphisms in nature.
- tetha 13y agoYup, doing a big of handwavy math also demonstrates this: You are comparing something like x^N - x^M with 2^x - x^M. The second will always grow big rapidly, while the first could stay small, but it can also grow arbitrarily large. In fact, it is bound to do so for N > M and it will do so quite rapidly if N >> M.
- Tmmrn 13y ago
- Aardwolf 13y agoA proof that P=NP without an accompanying program that solves SAT or another NP problem in polynomial time does not count to me :)
- raverbashing 13y agoI agree And let me say, I don't even care about a paper. Sure, it's useful, but it shouldn't be the focus. A simple implementation that solves any of the NP problems in polynomial time is a much better proof than any article. (of course, those that prove P != NP can't do that, still)
- aeurielesn 13y agoI beg to disagree with both of you. You are kinda disrespecting the important of theoretic research, and a big part of any field of interest on research.
- raverbashing 13y agoOh the theoretical aspect is important. But applying it is important as well. Of course, most quantum computing algorithms have not had a chance of being implemented; it's not always possible Or, as Knuth put it "Beware of bugs in the above code; I have only proved it correct, not tried it." But if someone comes up with a paper showing a new algorithm but doesn't come up with an implementation of it when it would be straightforward to do so, I begin to doubt this person. Most other fields don't have the luxury of easy testing.
- quchen 13y ago> A simple implementation that solves any of the NP problems in polynomial time is a much better proof than any article. That completely misses the point of P vs. NP, which is not about programmability but a problem entirely of theoretical nature (and interest). - O(n^<Graham's number>) is in P. (If you can solve TSM in that time, you've proven P = NP.) - Cracking AES-256 is even easier than P: it's O(1).
- pof33 13y agoLet's play a little game: Crank or No Crank.
- doughj3 13y agoHow did this go from being #3 on the front page of Hacker News to non-existent even two or three pages back?
- elwell 13y agoModeration
- simgidacav 13y agoEven if this content is quite old, the idea of linking it here in those days is quite clever. Just tell me how many of you did not immediately think "Oh crap, my RSA is doomed!".
- Houshalter 13y agoCryptography? Really? Wouldn't this mean you could create absurdly intelligent AIs and solve pretty much any optimization problem?