Hacker News Reader

Comment by allochthon | Hacker News Reader

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.

View on HN

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.

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.

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.

Reply on news.ycombinator.com