A proof P = NP was accidentally published in TOCT | Hacker News Reader

A proof P = NP was accidentally published in TOCT

twitter.com

112 pointsluu102 comments

Here is some additional context: https://twitter.com/rrwilliams/status/1417161397960646658

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.

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.

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.

I had never thought of P=NP or not being chosen by vote, but if it's formally undecidable, we might end up there.

what counts as a nontrivial proof? better submit this comment!

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.

Too late, no take backs. P now equals NP and we must live with the consequences!

BRB air gapping every single device I own and setting my internet router on fire. ;)

BRB computing several billion bitcoin hash completions on my Casio.

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?

Computing any hash isn't, but finding a preimage is NP.

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.

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).

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.

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.

That much was clear, and I believe also implied in my answers?

If what I said was your mental state then you are not wrong.

How will you be right back after that?

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.

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.

This is the way.

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.

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.

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?)

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.

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.

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.

The fivefold repetition rule requires no claim by the players.

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.

Thanks for explaining this, I learned something, too!

If the universe is finite, does that mean every problem is a constant time algorithm?

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.

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).

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.

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.

> random access to an infinite, uncomputable sequence.

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

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.

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/

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-)

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.

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?

> 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?

https://en.wikipedia.org/wiki/P_versus_NP_problem

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.

I thought it was, that the proof of equality would have to be a general algorithm to transform one into the other.

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.

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.

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?

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?

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.

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.

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.

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.

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.

Though if P = NP, the exponent could possibly very high, removing the practical effect.

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.

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

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.

O(n*1000000) is linear, polynomial would be O(N^Y), where Y is the degree of polynomial.

linear time complexity problems are a subset of polynomial time complexity problems, if we're being pedantic.

I think we can all agree that being pedantic is part of the foundation that makes HN be HN.

in the case where Y=1 you both agree.

O(n*1000000) is O(n) isn't it?

Yes

Right, but apparently Hacker News changes a * followed by another * into one *, even though several languages use two asterisks as the exponentiation operator.

Typo? Did you mean O(n^1000000) ?

No, I typed two '*' characters, and it appears that this site made one of them go away. I meant n to the millionth power.

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.

> 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.

> 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.

clickbait title. should start with "A rejected proof"

Probably not intentional. The HN filter drops quotes on single words (editing them will restore it).

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?

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...

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.

The paper on arxiv, if anyone wants to spot the error: https://arxiv.org/pdf/1004.3702.pdf

kind of light on the math considering what it's attempting to prove

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.)

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.

An old joke says that P = NP if N = 1

Here's the paper: https://www.researchgate.net/publication/351475502_A_polynom...

Are there examples of problems that were once thought to be NP but later turned out to be P?

Primality testing.

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

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.

Probably many people thought Majority-3SAT is PP-complete (even harder than NP)

But it is in P

An earlier version (2010) of the paper in arXiv:

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

Is it possible that P=NP is true but unprovable? And If that is the case, how do we prove it is unprovable?

Godel's incompleteness theorem shows that it's possible for any axiomatic system (like mathematics) to have statements that are true but unproveable.

But does it give a way of distinguishing which statements those are from other statements that are just not proven yet?

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 :)

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

We need a lot more peer review for academic papers.

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.

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.

The paper in question was desk rejected. This isn’t a failure of peer review, it’s a clerical error.

Or the author did solve P=NP, saw the rejection, and then broke the journal’s security to prove it was actually solved.

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.

> 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.

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.

Quick cite it before anybody notices

Reply on news.ycombinator.com