[HN Gopher] A proof P = NP was accidentally published in TOCT
___________________________________________________________________
A proof P = NP was accidentally published in TOCT
Author : luu
Score : 60 points
Date : 2021-07-19 20:25 UTC (2 hours ago)
(HTM) web link (twitter.com)
(TXT) w3m dump (twitter.com)
| latenightcoding wrote:
| clickbait title. should start with "A rejected proof"
| zinekeller wrote:
| Probably not intentional. The HN filter drops quotes on single
| words (editing them will restore it).
| allochthon wrote:
| Can 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.
| cakoose wrote:
| Whether P = NP is a long-standing problem. Like many long-
| standing problems, it's deceptively difficult, which results in
| many people incorrectly claiming they have solved it:
| https://www.scottaaronson.com/blog/?p=458
|
| A lot of cryptography relies on NP problems being difficult to
| solve. If someone figures out a way to solve NP problems in
| polynomial time, they may keep that technique to themselves
| rather than publish it. The rest of us might only become aware
| of this after we see real-world crypto being broken.
|
| In this particular case though, it was just another P = NP
| paper that was rejected, but accidentally got published.
| throwaway81523 wrote:
| 1. P vs NP is a famous open CS problem, which (like Fermat's
| last theorem back in the day) attracts a huge number of
| crackpots purporting to have proofs one way or the other. There
| is a million dollar reward (Clay Millenium Prize) for the first
| correct proof, but obviously it has not been paid out so far.
|
| 2. There are also some attempts by legitimate researchers (non-
| crackpot) but that also turn out to be wrong. You can see some
| examples of wrong proofs (most crackpot, some not) here:
| https://www.win.tue.nl/~gwoegi/P-versus-NP.htm
|
| 3. Someone submitted yet another "proof" to TOCT (legit
| journal). The journal presumably gets those all the time. They
| took a quick look at the manuscript and rejected it as usual.
| They are used to that.
|
| 4. Because of some kind of clerical error, the manuscript
| somehow found its way into TOCT's publication queue even though
| it had been rejected. This provoked the obvious WTF from people
| who saw it.
|
| 5. There are now some tweet threads etc. clearing up the
| confusion. It's just another bogus P vs NP proof, like the 100s
| that have already appeared. Nothing to write home about. This
| has been going on for decades.
| shadowgovt wrote:
| Are 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 wrote:
| > 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 wrote:
| https://en.wikipedia.org/wiki/P_versus_NP_problem
| LatteLazy wrote:
| I 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.
| DrBenCarson wrote:
| Proving it's possible is the hard part, though. Granted, if
| you did actually implement a P-time algorithm that would
| also do the former.
| dragontamer wrote:
| More importantly, if it turns out that P = NP through a
| O(n^1,000,000,000,000) algorithm, then you've proven P = NP
| but no one is breaking much security any time soon.
|
| But even finding a O(n^big_number) (where big_number is a
| googleplex, or graham's number... or some other absurdity)
| would be a huge advancement in theoretical computer
| science.
| nraynaud wrote:
| I thought it was, that the proof of equality would have to
| be a general algorithm to transform one into the other.
| csnweb wrote:
| There might be a possibility to prove that such an
| algorithm exists without knowing how the algorithm works
| exactly / being able to construct a runnable version of
| it.
| erik wrote:
| In theory a proof could show that such an algorithm must
| exist without producing the algorithm itself. Though
| that's not what this linked paper tries to do.
| lovecg wrote:
| In fact if there was a non-constructive proof, we would
| already know a polynomial time algorithm for solving any
| NP problem: just iterate over all program lengths (from 1
| to infinity) and then iterate over all programs of that
| length n, running each for n steps. If one of the guesses
| produces the correct answer (which it must if P = NP), we
| have a polynomial time algorithm! Wild, huh?
| ineedasername wrote:
| To very much over simplify:
|
| Some problem are "easy", there is a way to solve even complex
| ones with a (relatively) small amount of effort. These are P.
|
| Other problems have no known "easy" method and the solution to
| a given problem can only be determined by something like brute
| force, such as trying every possibility.
| not2b wrote:
| I 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.
| TrainedMonkey wrote:
| O(n*1000000) is linear, polynomial would be O(N^Y), where Y is
| the degree of polynomial.
| yifanl wrote:
| linear time complexity problems are a subset of polynomial
| time complexity problems, if we're being pedantic.
| ineedasername wrote:
| I think we can all agree that being pedantic is part of the
| foundation that makes HN be HN.
| shoo wrote:
| in the case where Y=1 you both agree.
| chrisseaton wrote:
| O(n*1000000) is O(n) isn't it?
| hosteur wrote:
| Yes
| emerged wrote:
| Too late, no take backs. P now equals NP and we must live with
| the consequences!
| ineedasername wrote:
| So 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 wrote:
| Chess 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.
| meepmorp wrote:
| This is the way.
| shadowgovt wrote:
| BRB air gapping every single device I own and setting my
| internet router on fire. ;)
| munk-a wrote:
| BRB computing several billion bitcoin hash completions on my
| Casio.
| anyfoo wrote:
| Serious question: Is computing cryptographic hashes, by any
| measure, actually NP-hard? Computing a single hash seems
| pretty constant to me. Or is there an alternative way to
| formulate the problem on a higher level, so that _cracking_
| cryptographic hashes is NP-hard?
| [deleted]
| staticassertion wrote:
| Computing any hash isn't, but finding a preimage is NP.
| anyfoo wrote:
| Can you elaborate? Is it because a non-deterministic
| automaton would find the solution immediately (by trying
| all hashes at once), but a deterministic one of course
| wouldn't? I think I want to know in more detail why
| finding a pre-image is non-deterministically polynomial
| (though I might have answered that to myself with the
| sentence before), and more importantly why it's
| deterministically non-polynomial, and on what.
| [deleted]
| shadowgovt wrote:
| You basically have the right idea. The pre-image can be
| any arbitrary size (in fact, there are an infinite number
| of pre-images that will hash to the same value).
|
| As useful rule of thumb, the way I learned to think about
| NP was the mnemonic "nifty proof." Problems in NP are not
| known to have a polynomial-time solution, and are not
| known to have _no_ polynomial time solution; that 's the
| million dollar question. What they _are_ known to have is
| a polynomial time validation.
|
| So it might take some heinous amount of time to find the
| pre-image of the hash, but determining if a given input
| string _is_ the pre-image of the hash is polynomial on
| the number of characters in the pre-image (just run the
| hash function).
| anyfoo wrote:
| Correct me if I'm wrong: So n is actually the size of the
| hash. That's indeed exponential if you try to brute force
| it, but a non-deterministic automaton would still give
| the answer immediately.
| smnrchrds wrote:
| How will you be right back after that?
| ineedasername wrote:
| Assuming supplies on hand?
|
| 1)A 5 gallon bucket of gasoline
|
| 2) a shop vac w/o a filter & the hose stuck in the bucket
| to disperse it into the air as a fine mist
|
| 3) a bottle rocket sent through the front door (from across
| the street, preferably)
|
| You know, I've never really though about how to make a
| homemade fuel air bomb before. It's a bit disturbing that
| it probably wouldn't be much harder than the above.
| tW4r wrote:
| Quick cite it before anybody notices
| ineedasername wrote:
| Are there examples of problems that were once _thought_ to be NP
| but later turned out to be P?
| jcranmer wrote:
| Primality testing.
| na85 wrote:
| For anyone like me who could only find snarky responses,
| including in this thread:
|
| https://www.quora.com/Why-does-proving-P-NP-break-cryptograp...
| gberger wrote:
| Here is some additional context:
| https://twitter.com/rrwilliams/status/1417161397960646658
| throwaway81523 wrote:
| Thanks, 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
|
| 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 wrote:
| This 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.
| ineedasername wrote:
| Thanks, 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.
| cscurmudgeon wrote:
| An earlier version (2010) of the paper in arXiv:
|
| https://arxiv.org/pdf/1004.3702.pdf
| spicybright wrote:
| We need a lot more peer review for academic papers.
| 542458 wrote:
| The paper in question was desk rejected. This isn't a failure
| of peer review, it's a clerical error.
| DrBenCarson wrote:
| Or the author did solve P=NP, saw the rejection, and then
| broke the journal's security to prove it was actually solved.
| [deleted]
| Jtsummers wrote:
| From 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 wrote:
| Luckily 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.
| H8crilA wrote:
| Don'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
|
| 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
| [deleted]
| jtsiskin wrote:
| The paper on arxiv, if anyone wants to spot the error:
| https://arxiv.org/pdf/1004.3702.pdf
| jcranmer wrote:
| At 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.)
| polynomial wrote:
| kind of light on the math considering what it's attempting to
| prove
___________________________________________________________________
(page generated 2021-07-19 23:02 UTC)