9 ms·
A proof P = NP was accidentally published in TOCT
- cscurmudgeon 5y agoAn earlier version (2010) of the paper in arXiv: https://arxiv.org/pdf/1004.3702.pdf https://arxiv.org/pdf/1004.3702.pdf
- H8crilA 5y agoDon't forget that this is the "holy grail" of amateur research. Here's a list of approx 100 papers proving all results for the hypothesis: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm https://www.win.tue.nl/~gwoegi/P-versus-NP.htm Scott Aaronson even has a checklist/rule-of-thumb-list for quickly determining that a paper on any of the big computational complexity claims is likely bogus. He has seen a ton of those :) https://www.scottaaronson.com/blog/?p=458 https://www.scottaaronson.com/blog/?p=458
- gberger 5y agoHere is some additional context: https://twitter.com/rrwilliams/status/1417161397960646658 https://twitter.com/rrwilliams/status/1417161397960646658
- ineedasername 5y agoThanks, that makes a lot more sense. I was surprised to see ACM on there because if they were even close to publishing something like that it would already be making massive waves.
- throwaway81523 5y agoThanks, that is a tweet by Ryan Williams (complexity theorist extraordinaire) who is on the editorial board of that journal, confirming that the paper was rejected, then accidentally dropped into the publish queue. A better publication venue might have been here: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm https://www.win.tue.nl/~gwoegi/P-versus-NP.htm That page links to a lot of P=NP proofs and also P!=NP proofs. I haven't counted them up lately so I don't know which is ahead.
- jvanderbot 5y agoThis entry from the survey was my favorite: Prediction by Richard Chang:(Univ of MD Balt County, 2066, P6=NP) In the year, 2066 the idea that computers will double in speed every 18 months (Moore’s Law) has been ludicrous for 50years. As such, no one uses asymptotic analysis anymore. Programs are written in assembly language to shave the running time. Some poor assistant professor will prove that P != NP and fail to get tenure for it Though I would guess predictive programming and execution would look more like an AI system and would be clawing at throughput gains by "learning" how the programmer of the current program expected things to go ... rather than the programmer working in ASM to make it so.
- jl2718 5y agoIf it gets to that point, which I think it will, then the there will be no such thing as an instruction set. Computing will be reconfigurable asynchronous data flow.
- ncmncm 5y agoI had never thought of P=NP or not being chosen by vote, but if it's formally undecidable, we might end up there.
- cyanydeez 5y agowhat counts as a nontrivial proof? better submit this comment!
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- spicybright 5y agoWe need a lot more peer review for academic papers.
- Jtsummers 5y agoFrom the tweet linked by gberger, it seems this was rejected but ended up in the publish queue by error. Sounds like a procedural error, I'm curious what their process looks like now.
- bryanrasmussen 5y agoLuckily the AIs we will be able to build now that P = NP means that this kind of error can be caught by the machines in the future.
- 542458 5y agoThe paper in question was desk rejected. This isn’t a failure of peer review, it’s a clerical error.
- DrBenCarson 5y agoOr the author did solve P=NP, saw the rejection, and then broke the journal’s security to prove it was actually solved.
- omaranto 5y agoDoes "desk-rejected" mean it was rejected by an editor who decided the paper was so wrong it wasn't even necessary to get a referee report? (I am familiar with the scientific publication process being a mathematician, but have never seen the term "desk-rejected" before, it may be a CSism.) EDIT: Huh, "desk-rejected" is a common term not just in CS but also in medicine and other fields. It means, as I thought, rejected by an editor without even getting a referee report. I do think even though that thing does happen in math, the term "desk-rejection" is not used.
- paulddraper 5y ago
- latenightcoding 5y agoclickbait title. should start with "A rejected proof"
- zinekeller 5y agoProbably not intentional. The HN filter drops quotes on single words (editing them will restore it).
- allochthon 5y agoCan someone in the know unpack what's going on here for a less-informed audience? I know vaguely about the outstanding question of whether P = NP, and how it's generally thought that P is not equal to NP. But beyond that most of the context here is unknown to me.
- shadowgovt 5y agoAre you looking for context regarding how this proof ended up in a prestigious academic journal (when the journal had already planned to reject it) or a more general overview of why any proof that P=NP will likely show up first not in an academic journal, but in a catastrophically massive security breach that lays bare all of the secret information from multiple organizations simultaneously?
- allochthon 5y ago> a more general overview of why any proof that P=NP will likely show up first not in an academic journal, but in a catastrophically massive security breach that lays bare all of the secret information from multiple organizations simultaneously? This is probably what I was looking for. Is there a good discussion of this topic?
- herodotus 5y agohttps://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem
- LatteLazy 5y agoI don't think a proof that P=NP is the same as actually turning all NP problems into P problems. You could prove it's POSSIBLE to break all current security without actually breaking any of it.
- nraynaud 5y agoI thought it was, that the proof of equality would have to be a general algorithm to transform one into the other.
- emerged 5y agoToo late, no take backs. P now equals NP and we must live with the consequences!
- ineedasername 5y agoSo much for chess. Instead of memorizing countless games, expert players will all just memorize the algorithm, and winning will come down to a coin flip of who goes first.
- jcranmer 5y agoChess is EXPTIME, not NP. Unless you want to consider that it's only played on a fixed-size board, in which case it's actually a constant-time algorithm.
- ineedasername 5y agoAh, thanks. I like being wrong on HN because I learn things. What's most interesting to me is why I was wrong, so I'll share: I was thinking in terms of infinite moves when I should have been thinking in terms of non-infinite board states: A move, though possibly part of an infinite series of moves, is still only one of a finite number of states for the board. And each state can theoretically be evaluated to results in a win/lose/draw for either white/black assuming both player play a perfect game. Now I'm going to go way outside my comfort zone with the hope of correction or confirmation: Since the nature of chess on a board of of N dimensions is EXPTIME-hard, would chess on an infinite board be NEXPTIME-hard? (And if not, what level of the time hierarchy would that fall under?)
- PeterisP 5y agoChess also has a finite number of moves (at least on a finite board), the 50-move rule and the 3-repetition rule ensure that a game can't last infinitely even if both players want to and ends in a forced draw.
- 5y ago
- tW4r 5y agoQuick cite it before anybody notices
- na85 5y agoFor anyone like me who could only find snarky responses, including in this thread: https://www.quora.com/Why-does-proving-P-NP-break-cryptography https://www.quora.com/Why-does-proving-P-NP-break-cryptograp...
- bawolff 5y agoCryptography is the least of the things that would earth shatteringly change if we had a constructive proof that P=NP (with reasonable exponents). https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem Is a good starting place for info on the problem.
- jtsiskin 5y agoThe paper on arxiv, if anyone wants to spot the error: https://arxiv.org/pdf/1004.3702.pdf https://arxiv.org/pdf/1004.3702.pdf
- polynomial 5y agokind of light on the math considering what it's attempting to prove
- jcranmer 5y agoAt first glance, it's trying to solve 3SAT by using a 2SAT algorithm. I haven't followed it in detail, but my guess is that the error is that the algorithm accumulates an exponential set of possibilities rather than a polynomial set. (It's a bit hard to follow due to excessive use of custom terminology.)
- userbinator 5y agoWhat I immediately noticed as strange is the author is from a university in Wuhan, and has a Yahoo email address listed prominently, then at the bottom what appears to be his actual university email address in a footnote.
- not2b 5y agoI believe that P != NP. But suppose someone finds a way to provably solve SAT in O(n**1000000), thus proving P = NP. It's polynomial, but still unusable for real problems. Edit: fixing damage to my post by Hacker News, making people think I don't understand O-notation.
- chrisseaton 5y agoO(n*1000000) is O(n) isn't it?
- TrainedMonkey 5y agoO(n*1000000) is linear, polynomial would be O(N^Y), where Y is the degree of polynomial.
- shoo 5y agoin the case where Y=1 you both agree.
- yifanl 5y agolinear time complexity problems are a subset of polynomial time complexity problems, if we're being pedantic.
- ineedasername 5y agoI think we can all agree that being pedantic is part of the foundation that makes HN be HN.
- ineedasername 5y agoAre there examples of problems that were once thought to be NP but later turned out to be P?
- jcranmer 5y agoPrimality testing.
- krasin 5y agoYep, the AKS primality test (2002) was such a surprise to many (including myself) at the time. Most importantly, it did not rely on Riemann hypothesis, which remains unresolved. 1. https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test
- CaptainNegative 5y agoTechnically speaking, every problem in P is thought to (and known to) be in both P and NP. You're probably asking about NP-hard problems, where the answer might be no. Primality (which others refer to) was thought to be outside of P, but I'm not sure it was a common conjecture that it was NP hard. The existence of a simple certificate of compositeness places the problem in Co-NP, and so it would have quickly been deduced that Primality is NP-hard only if NP = Co-NP, which I don't think was ever a particularly common conjecture. Pratt found his primality certificate only a couple years after Karp published his famous paper, so I don't expect compositeness was widely thought to be NP-hard, either.
- benibela 5y agoProbably many people thought Majority-3SAT is PP-complete (even harder than NP) But it is in P
- deleted 5y ago[deleted]
- kuczmama 5y agoHere's the paper: https://www.researchgate.net/publication/351475502_A_polynomial_time_algorithm_for_3SAT_the_newest_version_of_May_2021 https://www.researchgate.net/publication/351475502_A_polynom...
- nsoonhui 5y agoThe journal made a mistake, an unintentional one. It got corrected and we should just move on. As for the author, instead of outing him and humiliating him, he should at least be commended for trying hard on a hard problem-- you can't do that without dedication and zeal. So why so snarky?
- deleted 5y ago[deleted]
- ivanche 5y agoAn old joke says that P = NP if N = 1
- RavlaAlvar 5y agoIs it possible that P=NP is true but unprovable? And If that is the case, how do we prove it is unprovable?
- natarajanda 5y agoGodel's incompleteness theorem shows that it's possible for any axiomatic system (like mathematics) to have statements that are true but unproveable.
- kbelder 5y agoBut does it give a way of distinguishing which statements those are from other statements that are just not proven yet?
- kolinko 5y agoA way for distinguishing = a way to prove. Some things can be provably unprovable, but there will always be things that are unprovably unprovable. And unprovably unprovably unprovable :)
- mgsouth 5y agoIf you're asking "is this statement true but unprovable", then no, that would itself be a proof. It is possible to show that, within a particular set of mathematical rules, some statements are "either true or false, but we'll never be able to prove which." An example is the parallel postulate ("parallel lines neither converge nor diverge at infinity") [0]. This is impossible to either prove or disprove in Euclidian geometry, and has to be taken as a given truth. Interestingly, showing a statement is unprovable implies that you can postulate either way (true or false) and still have a self-consistent mathematical structure. (If you assumed one way, and ran into an inconsistency, then that would be a proof the assumption is false and the opposite choice is true.) So if you assume the parallel postulate is true you get Euclidean geometry. If you assume false you get a non-Euclidean geometry such as Elliptic, Spherical, or Hyperbolic (depending on what additional postulates you choose). [0] https://en.wikipedia.org/wiki/Parallel_postulate https://en.wikipedia.org/wiki/Parallel_postulate