News for hackers. Stuff that matters.
Re:A proof P = NP was accidentally published in TOCT by gberger on Monday July 19, 2021 @05:11PM (#27887299)
Re:A proof P = NP was accidentally published in TOCT by throwaway81523 on Monday July 19, 2021 @05:49PM (#27887641)
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.

Re:A proof P = NP was accidentally published in TOCT by jvanderbot on Monday July 19, 2021 @06:00PM (#27887755)
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.

Re:A proof P = NP was accidentally published in TOCT by jl2718 on Tuesday July 20, 2021 @10:22PM (#27901659)
If 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.
Re:A proof P = NP was accidentally published in TOCT by ncmncm on Monday July 19, 2021 @09:55PM (#27889342)
I had never thought of P=NP or not being chosen by vote, but if it's formally undecidable, we might end up there.
Re:A proof P = NP was accidentally published in TOCT by cyanydeez on Monday July 19, 2021 @10:14PM (#27889447)
what counts as a nontrivial proof? better submit this comment!
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:08PM (#27887840)
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.
Re:A proof P = NP was accidentally published in TOCT by emerged on Monday July 19, 2021 @05:28PM (#27887457)
Too late, no take backs. P now equals NP and we must live with the consequences!
Re:A proof P = NP was accidentally published in TOCT by mikewarot on Monday July 19, 2021 @08:18PM (#27888798)
While we're at it... the halting problem CAN be solved, for a computer with N bits of state, in a time proportional to 2^N.

It remains unsolvable for Turing machines, however. 8-)

Re:A proof P = NP was accidentally published in TOCT by shadowgovt on Monday July 19, 2021 @05:31PM (#27887484)
BRB air gapping every single device I own and setting my internet router on fire. ;)
Re:A proof P = NP was accidentally published in TOCT by munk-a on Monday July 19, 2021 @05:53PM (#27887673)
BRB computing several billion bitcoin hash completions on my Casio.
Re:A proof P = NP was accidentally published in TOCT by anyfoo on Monday July 19, 2021 @06:03PM (#27887778)
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?
Re:A proof P = NP was accidentally published in TOCT by staticassertion on Monday July 19, 2021 @06:07PM (#27887835)
Computing any hash isn't, but finding a preimage is NP.
Re:A proof P = NP was accidentally published in TOCT by anyfoo on Monday July 19, 2021 @06:17PM (#27887939)
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.

Annoying, I took theoretical computer science in university and used to have a better grasp on this, but apparently that part of complexity theory atrophied by now.

Re:A proof P = NP was accidentally published in TOCT by shadowgovt on Monday July 19, 2021 @06:40PM (#27888111)
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).

Re:A proof P = NP was accidentally published in TOCT by anyfoo on Monday July 19, 2021 @06:43PM (#27888136)
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.
Re:A proof P = NP was accidentally published in TOCT by freemint on Tuesday July 20, 2021 @06:18AM (#27891931)
A non-deterministic automata can you give an answer after n steps which is polynomial.

NP is the class of problems that can be solved in polynomial time by a non-deterministic automaton.

Re:A proof P = NP was accidentally published in TOCT by anyfoo on Tuesday July 20, 2021 @02:38PM (#27897494)
That much was clear, and I believe also implied in my answers?
Re:A proof P = NP was accidentally published in TOCT by freemint on Tuesday July 20, 2021 @04:59PM (#27899250)
If what I said was your mental state then you are not wrong.
Re:A proof P = NP was accidentally published in TOCT by smnrchrds on Monday July 19, 2021 @05:57PM (#27887723)
How will you be right back after that?
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:16PM (#27887925)
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.

Re:A proof P = NP was accidentally published in TOCT by BenjiWiebe on Tuesday July 20, 2021 @01:41PM (#27896751)
The shop vac would probably actually ignite the fumes. And I think the GP was referring to the inability to be right back (here, online) after destroying his internet connection.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:11PM (#27887877)
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.
Re:A proof P = NP was accidentally published in TOCT by jcranmer on Monday July 19, 2021 @06:35PM (#27888067)
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.

Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @07:20PM (#27888390)
Ah, 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?)

Re:A proof P = NP was accidentally published in TOCT by PeterisP on Monday July 19, 2021 @07:34PM (#27888498)
Chess 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.
Re:A proof P = NP was accidentally published in TOCT by agalunar on Monday July 19, 2021 @08:09PM (#27888731)
It's actually because of the 5-fold repetition and 75-move rules! The game is not necessarily over at 3 and 50 – you merely have the right to claim a draw.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @08:55PM (#27889015)
Both of those require a player to claim the draw. There is no reason within the rules of the game for why it could not be infinite in the # of moves. The rule has also at times been restricted only to tournament play.

Also, if chess was "solved" and board states determined "winnable" after significantly more moves, the rules might very well change to extend that limit.

Something along those lines has happened before: When a combination of pieces have been shown to be "winnable" but might exceed the 50 move rule, exceptions have been made to the rule to allow more time to develop the win. At some point though, the rules went back to 50, but still with conditions about pawn moves, pieces taken, etc.

The history is interesting: 50 was originally chosen (or maybe just compromised on) because players felt than all winnable games could be won in 50 moves or under.

Re:A proof P = NP was accidentally published in TOCT by pentestercrab on Monday July 19, 2021 @09:43PM (#27889280)
The fivefold repetition rule requires no claim by the players.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Tuesday July 20, 2021 @07:06PM (#27900400)
Ah, true... Given the double criteria for that (lack of pawn movement) it extends things a bit, but there would still be a finite number of moves.

However on an info it's chess board there would always be a unique board state possible. That doesn't by any means refute your point, only add a twist to things.

Re:A proof P = NP was accidentally published in TOCT by elliekelly on Tuesday July 20, 2021 @09:57AM (#27893770)
Thanks for explaining this, I learned something, too!
Re:A proof P = NP was accidentally published in TOCT by mrfusion on Monday July 19, 2021 @07:53PM (#27888622)
If the universe is finite, does that mean every problem is a constant time algorithm?
Re:A proof P = NP was accidentally published in TOCT by davrosthedalek on Tuesday July 20, 2021 @08:08AM (#27892755)
I think you also need to assume that spacetime is discretized. Otherwise, two particles have already an infinite phase space (their distance). I don't think the uncertainty principle is enough.
Re:A proof P = NP was accidentally published in TOCT by emerged on Monday July 19, 2021 @09:26PM (#27889200)
We do seem to spend an awful lot of time worrying about infinities when it appears the cosmological horizon is finite. But I guess if we find some way around that we will be prepared.
Re:A proof P = NP was accidentally published in TOCT by raattgift on Tuesday July 20, 2021 @06:27AM (#27892011)
In an accelerating expanding universe like the one we appear to occupy (and the one modelled by our current "concordance" standard model of comology), the comoving horizon is at constant comoving distance. Cast into more Earth-centric coordinates, it is at a finite spatial distance at all finite times.

However, there is no reason to expect that a timelike worldline rooted at "here and now" (converting a chosen comoving coordinate into the origin of spherical coordinates for a Eulerian observer) cannot be extended into the infinite future, and at +infinite time the horizon will be at an infinite spatial distance in this system of coordinates. We don't even need to say anything about the matter content of the Hubble volume at any time, anything about -infinite time, or anything about how various measures of entropy fit in; all of these can generate infinities that defy easy (and possibly any) removal in a universe similar to the concordance model.

A taste of this can be found at https://en.wikipedia.org/wiki/Cosmological_horizon#Future_ho...

More deeply and technically, Baez's "Struggles with the Continuum" is great A smooth manifold tends to generate infinities and infinitesimals, and all our fundamental physical descriptions of the universe we inhabit are (at least at present) defined on a Lorentzian spacetime, which is a smooth manifold. He discusses practical reasons to [a] worry about infinities and [b] to work with them anywhere because they might not be removable. https://arxiv.org/abs/1609.01421 (§5 starting on p. 27 is directly relevant, and the concluding §6 is pithy).

Re:A proof P = NP was accidentally published in TOCT by bawolff on Monday July 19, 2021 @11:43PM (#27889838)
No,because you don't have to execute a procedure in order to construct it.

I.e. we can talk about Turing machines with infinite tapes without actually making one with an infinite tape.

Re:A proof P = NP was accidentally published in TOCT by Hercuros on Tuesday July 20, 2021 @02:37AM (#27890711)
It's also important to realize that the standard Turing machine doesn't actually have an infinite tape, but rather it has a tape that can grow to hold an arbitrarily long, but still finite, sequence. At any point during the execution of the Turing machine, only a finite part of the tape will be occupied.

So we can construct approximations of it in the sense that we can create computers with varying, finite amounts of RAM. This might seem like a pedantic/obvious point to make, but it is actually also possible to design abstract computational machines that operate on truly infinite quantities, like a machine that has random access to an infinite, uncomputable sequence.

From a simplicity perspective, it also makes more sense to consider machines with an arbitrarily large amount of RAM (you can always hotplug more RAM), compared to setting some arbitrary limit because that is the most RAM we happen to be able to achieve in this universe.

Re:A proof P = NP was accidentally published in TOCT by hypertele-Xii on Tuesday July 20, 2021 @05:49AM (#27891753)
> random access to an infinite, uncomputable sequence.

I.e. a (cryptographic) random number generator?

Re:A proof P = NP was accidentally published in TOCT by colejohnson66 on Tuesday July 20, 2021 @09:31AM (#27893444)
That’s already a thing with Tic-Tac-Toe.[0] Granted, Tic-Tac-Toe is exponentially less complicated than Chess.

[0]: https://xkcd.com/832/

Re:A proof P = NP was accidentally published in TOCT by meepmorp on Monday July 19, 2021 @05:58PM (#27887739)
This is the way.
Re:A proof P = NP was accidentally published in TOCT by allochthon on Monday July 19, 2021 @05:26PM (#27887436)
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.
Re:A proof P = NP was accidentally published in TOCT by throwaway81523 on Monday July 19, 2021 @05:55PM (#27887691)
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.

Re:A proof P = NP was accidentally published in TOCT by cakoose on Monday July 19, 2021 @06:16PM (#27887928)
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.

Re:A proof P = NP was accidentally published in TOCT by paulddraper on Monday July 19, 2021 @09:09PM (#27889095)
Though if P = NP, the exponent could possibly very high, removing the practical effect.
Re:A proof P = NP was accidentally published in TOCT by shadowgovt on Monday July 19, 2021 @05:30PM (#27887475)
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?
Re:A proof P = NP was accidentally published in TOCT by allochthon on Monday July 19, 2021 @05:32PM (#27887491)
> 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?

Re:A proof P = NP was accidentally published in TOCT by herodotus on Monday July 19, 2021 @05:37PM (#27887534)
Re:A proof P = NP was accidentally published in TOCT by LatteLazy on Monday July 19, 2021 @05:36PM (#27887522)
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.
Re:A proof P = NP was accidentally published in TOCT by dragontamer on Monday July 19, 2021 @05:57PM (#27887726)
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.

Re:A proof P = NP was accidentally published in TOCT by DrBenCarson on Monday July 19, 2021 @05:50PM (#27887645)
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.
Re:A proof P = NP was accidentally published in TOCT by nraynaud on Monday July 19, 2021 @05:42PM (#27887587)
I thought it was, that the proof of equality would have to be a general algorithm to transform one into the other.
Re:A proof P = NP was accidentally published in TOCT by erik on Monday July 19, 2021 @05:52PM (#27887669)
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.
Re:A proof P = NP was accidentally published in TOCT by lovecg on Monday July 19, 2021 @06:05PM (#27887802)
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?
Re:A proof P = NP was accidentally published in TOCT by CaptainNegative on Monday July 19, 2021 @08:50PM (#27888992)
This finds a certificate for positive instances, but without a complexity bound can this be made to solve the decision problem in the presence of negative instances?
Re:A proof P = NP was accidentally published in TOCT by lovecg on Monday July 19, 2021 @09:40PM (#27889263)
I had to look this up since it’s been a while, but looks like no - this is not a full solution. It correctly accepts the positive instances in polynomial time but no algorithm is known that would fully decide all instances in polynomial time.
Re:A proof P = NP was accidentally published in TOCT by csnweb on Monday July 19, 2021 @05:51PM (#27887659)
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.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:25PM (#27887991)
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.

Re:A proof P = NP was accidentally published in TOCT by H8crilA on Monday July 19, 2021 @06:09PM (#27887859)
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

Re:A proof P = NP was accidentally published in TOCT by not2b on Monday July 19, 2021 @05:56PM (#27887708)
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.

Edit: fixing damage to my post by Hacker News, making people think I don't understand O-notation.

Re:A proof P = NP was accidentally published in TOCT by DrBenCarson on Monday July 19, 2021 @11:39PM (#27889824)
If SAT is solvable in polynomial time it’s only a matter of time until we have drastically better solutions than Y=1000000. Not only that, every commercial server in the world is optimized for long-running P-time implementations.

Everything in the digital world relies on P =/= NP. If that falls apart, we go back to the drawing board and start over.

Re:A proof P = NP was accidentally published in TOCT by dllthomas on Tuesday July 20, 2021 @01:36AM (#27890418)
> it’s only a matter of time until we have drastically better solutions than Y=1000000

Why? I'm likely missing something (and I'd love to know what!) but it seems plenty possible that some group of problems have a lower bound that's polynomial and still big.

Re:A proof P = NP was accidentally published in TOCT by throwaway81523 on Tuesday July 20, 2021 @03:47AM (#27891007)
> it seems plenty possible that some group of problems have a lower bound that's polynomial and still big.

Yes, that is a definite fact: https://en.wikipedia.org/wiki/Time_hierarchy_theorem

10000000 isn't that big a number anyway. We may be up against horrendous numbers that are so large that there is no concise way to write them down, even with recursive formulas such as Ackermann's function, or that sort of thing.

Re:A proof P = NP was accidentally published in TOCT by TrainedMonkey on Monday July 19, 2021 @06:01PM (#27887764)
O(n*1000000) is linear, polynomial would be O(N^Y), where Y is the degree of polynomial.
Re:A proof P = NP was accidentally published in TOCT by yifanl on Monday July 19, 2021 @06:04PM (#27887789)
linear time complexity problems are a subset of polynomial time complexity problems, if we're being pedantic.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:19PM (#27887952)
I think we can all agree that being pedantic is part of the foundation that makes HN be HN.
Re:A proof P = NP was accidentally published in TOCT by shoo on Monday July 19, 2021 @06:05PM (#27887812)
in the case where Y=1 you both agree.
Re:A proof P = NP was accidentally published in TOCT by chrisseaton on Monday July 19, 2021 @06:05PM (#27887809)
O(n*1000000) is O(n) isn't it?
Re:A proof P = NP was accidentally published in TOCT by hosteur on Monday July 19, 2021 @06:53PM (#27888214)
Yes
Re:A proof P = NP was accidentally published in TOCT by not2b on Monday July 19, 2021 @07:37PM (#27888515)
Right, but apparently Hacker News changes a * followed by another * into one *, even though several languages use two asterisks as the exponentiation operator.
Re:A proof P = NP was accidentally published in TOCT by inspector-g on Monday July 19, 2021 @07:13PM (#27888335)
Typo? Did you mean O(n^1000000) ?
Re:A proof P = NP was accidentally published in TOCT by not2b on Monday July 19, 2021 @07:35PM (#27888505)
No, I typed two '*' characters, and it appears that this site made one of them go away. I meant n to the millionth power.
Re:A proof P = NP was accidentally published in TOCT by latenightcoding on Monday July 19, 2021 @05:19PM (#27887370)
clickbait title. should start with "A rejected proof"
Re:A proof P = NP was accidentally published in TOCT by zinekeller on Monday July 19, 2021 @05:23PM (#27887417)
Probably not intentional. The HN filter drops quotes on single words (editing them will restore it).
Re:A proof P = NP was accidentally published in TOCT by nsoonhui on Monday July 19, 2021 @10:40PM (#27889552)
The 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?

Re:A proof P = NP was accidentally published in TOCT by na85 on Monday July 19, 2021 @05:38PM (#27887541)
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...

Re:A proof P = NP was accidentally published in TOCT by bawolff on Monday July 19, 2021 @11:52PM (#27889884)
Cryptography 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

Is a good starting place for info on the problem.

Re:A proof P = NP was accidentally published in TOCT by jtsiskin on Monday July 19, 2021 @05:45PM (#27887608)
The paper on arxiv, if anyone wants to spot the error: https://arxiv.org/pdf/1004.3702.pdf
Re:A proof P = NP was accidentally published in TOCT by jcranmer on Monday July 19, 2021 @06:44PM (#27888138)
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.)
Re:A proof P = NP was accidentally published in TOCT by userbinator on Monday July 19, 2021 @07:33PM (#27888490)
What 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.
Re:A proof P = NP was accidentally published in TOCT by polynomial on Monday July 19, 2021 @05:54PM (#27887687)
kind of light on the math considering what it's attempting to prove
Re:A proof P = NP was accidentally published in TOCT by ivanche on Tuesday July 20, 2021 @05:27AM (#27891601)
An old joke says that P = NP if N = 1
Re:A proof P = NP was accidentally published in TOCT by kuczmama on Monday July 19, 2021 @07:47PM (#27888585)
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:26PM (#27888008)
Are there examples of problems that were once thought to be NP but later turned out to be P?
Re:A proof P = NP was accidentally published in TOCT by CaptainNegative on Monday July 19, 2021 @08:55PM (#27889021)
Technically 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.

Re:A proof P = NP was accidentally published in TOCT by jcranmer on Monday July 19, 2021 @06:27PM (#27888015)
Primality testing.
Re:A proof P = NP was accidentally published in TOCT by krasin on Monday July 19, 2021 @07:34PM (#27888496)
Yep, 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

Re:A proof P = NP was accidentally published in TOCT by benibela on Tuesday July 20, 2021 @10:13AM (#27893960)
Probably many people thought Majority-3SAT is PP-complete (even harder than NP)

But it is in P

Re:A proof P = NP was accidentally published in TOCT by cscurmudgeon on Monday July 19, 2021 @06:05PM (#27887811)
An earlier version (2010) of the paper in arXiv:

https://arxiv.org/pdf/1004.3702.pdf

Re:A proof P = NP was accidentally published in TOCT by RavlaAlvar on Tuesday July 20, 2021 @06:16AM (#27891920)
Is it possible that P=NP is true but unprovable? And If that is the case, how do we prove it is unprovable?
Re:A proof P = NP was accidentally published in TOCT by natarajanda on Tuesday July 20, 2021 @07:44AM (#27892547)
Godel's incompleteness theorem shows that it's possible for any axiomatic system (like mathematics) to have statements that are true but unproveable.
Re:A proof P = NP was accidentally published in TOCT by kbelder on Tuesday July 20, 2021 @12:06PM (#27895517)
But does it give a way of distinguishing which statements those are from other statements that are just not proven yet?
Re:A proof P = NP was accidentally published in TOCT by mgsouth on Tuesday July 20, 2021 @03:06PM (#27897847)
If 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

Re:A proof P = NP was accidentally published in TOCT by kolinko on Tuesday July 20, 2021 @12:28PM (#27895860)
A 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 :)
Re:A proof P = NP was accidentally published in TOCT by spicybright on Monday July 19, 2021 @05:15PM (#27887333)
We need a lot more peer review for academic papers.
Re:A proof P = NP was accidentally published in TOCT by 542458 on Monday July 19, 2021 @05:20PM (#27887376)
The paper in question was desk rejected. This isn’t a failure of peer review, it’s a clerical error.
Re:A proof P = NP was accidentally published in TOCT by DrBenCarson on Monday July 19, 2021 @05:52PM (#27887670)
Or the author did solve P=NP, saw the rejection, and then broke the journal’s security to prove it was actually solved.
Re:A proof P = NP was accidentally published in TOCT by omaranto on Monday July 19, 2021 @07:24PM (#27888423)
Does "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.

Re:A proof P = NP was accidentally published in TOCT by shusaku on Tuesday July 20, 2021 @05:26AM (#27891590)
Just an FYI, desk rejected can happen even for a good paper if the editor doesn’t see it as being in the scope of the journal. But in this case you’re surely right.
Re:A proof P = NP was accidentally published in TOCT by paulddraper on Monday July 19, 2021 @09:11PM (#27889103)
> Does "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?

Yep.

Re:A proof P = NP was accidentally published in TOCT by Jtsummers on Monday July 19, 2021 @05:16PM (#27887341)
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.
Re:A proof P = NP was accidentally published in TOCT by bryanrasmussen on Monday July 19, 2021 @05:37PM (#27887529)
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.
Re:A proof P = NP was accidentally published in TOCT by tW4r on Monday July 19, 2021 @05:31PM (#27887480)
Quick cite it before anybody notices