Hacker News Reader

Comment by RSchaeffer | Hacker News Reader

Can someone ELI5 what this problem is, how likely the proof is to hold up to scrutiny, and whether P != NP follows?

Here is a largely correct ELI5: P != NP asks the question "Are problems that are easy to verify (NP) also Easy to solve? (P)".

Note that the reverse is obviously true: problems that are easy to solve are also easy to verify.

Here is an example: Take the problem "Find minimum of 5,6,7,8". You solve the problem and tell me that the answer is 5. I can verify your answer by solving the problem myself, getting the the answer 5 and comparing it with your answer. So we can conclude "Problems that are easy to solve are easy to verify" In other words, P ⊆ NP.

_Now is the reverse true? Are problems that are easy to verify also easy to solve?_

Let me give you an example. Let us assume that the question is "Is 1053188576519689 prime?". You come back and tell me, "No it is not prime, it is divisible by 32,452,867".

1) It is easy to verify your solution. I can divide 1053188576519689 by 32,452,867 and verify that it is indeed divisible. 2) It is hard to solve the problem, I have to try out numbers from 2,3,...,sqrt(1053188576519689), which is quite painful. (Or maybe there is as yet undiscovered better algorithm). So it appears that problems that are easy to verify may not be easy to solve. Or it appears that NP ⊆ P is not true. In other words, it appears P != NP (because if P ⊆ NP and NP ⊆ P, P == NP).

NP problems have wide ranging applications in things like cryptography for example. Let us assume I have a hashing technique. It is easy to hash a document, but hard to reconstruct the document from the hash. Then this technique can be used in auctions where you do not trust the auctioneer. You publicly submit the hash of your bid before the deadline. You do not submit your bid itself, because you are afraid that the person handing out the contracts will reveal the number to his brother-in-law who will bid $1 more than you and win the contract. After the deadline is passed, you send your actual bid to the Auctioneer.

Now 1) Everyone can verify that the documents have not been altered (the hashes are posted publicly, each document can be hashed and compared with its publicly posted hash). So it is easy to verify that the documents have not been tampered with after the deadline.

2) Nobody can construct the document from the hash. So it is not easy to solve for the bid document given the hash. So everyone can post the hash publicly with confidence before the deadline.

If P != NP we can have this type of auctions. If P == NP then there is no difference between posting the hash publicly and posting the document publicly.

(You may have omitted this detail on purpose, but I think it's worth pointing out) The example of trial division as a primality test is a good illustration of an algorithm that takes a lot of work to run but whose output is easy to verify. However, the problem of primality testing is actually in P. [1] You have to use a fancier algorithm than trial division in order to get polynomial time.

[1] https://en.wikipedia.org/wiki/AKS_primality_test

another detail that the GP most likely left out on purpose is that the fact that easily checking divisibility means that primality is co-NP. Primality being NP is actualy non-trivial (even before AKS). see wikipedia for more details: https://en.m.wikipedia.org/wiki/Primality_certificate

This is a good example of Knuth's argument that some P=NP proof by non construction or massive polynomial could play out

https://cs.stackexchange.com/questions/23260/when-is-the-aks...

I want to add another important aspect, the aspect of NP completeness. There is a bunch of problems considered "NP complete" and they are all related such that it is easy to translate one problem into another (easy as in "quickly").

This means, first: If P == NP, then all of these problems become easy, and second: if P == NP and we find an algorithm that solves only one of the NP complete problems quickly, then this algorithm can solve all algorithms quickly.

Reversely, if now this paper's proof is correct so P != NP, then there is no algorithm that solves any of these problems quickly.

NP completeness kinda works around the uncertainty of PxNP (with x ∈ {⊆, ⊊}), because it defines some sort of "weak subset" of NP comprised of "pretty sure these problems are not in P[, because no one yet thought of a polynomial reduction to a problem in P]". The last part in brackets is the catch here; if we could show that it is not possible, then P!=NP would immediately follow, and NP completeness would become a largely pointless exercise.

NP completeness would still be of interest for particular algorithms because it would prove that those problems could not be solved in polynomial time. For instance, if factoring was shown to be NP complete, that would be a really useful result both for showing the security of algorithms like RSA as well as potentially disproving the extended Church-Turing thesis if quantum computers can be created.

Also wanted to say:

People have been taking a go at this for many years now. Grapevine says that several large CS departments in many countries have groups of graduate students devoted to solving sub-problems of the entire proof because it is a prestige issue. Extraordinary claims require extraordinary proof and any proof will go through multiple peer reviews.

Perelman's proof of Poincare Conjecture was studied for several months before being declared true (~3 years) and that was considered "fast". https://en.wikipedia.org/wiki/Grigori_Perelman#Perelman.27s_...

No TCS grad student I have talked to has had this experience...

Almost everybody in the field knows we're far from an actual proof with current techniques.

I should have been more precise. By problem, I was referring to whatever, "Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev's function," means, not "P ? NP."

Let me take a stab at explaining that, although I'm not really an expert and probably misunderstanding something. Hopefully someone else will be able to correct me where I'm wrong.

The clique function takes a bit string representation of a graph with m nodes (one bit for each pair of nodes, 1s where there is an edge between two nodes) and outputs whether the graph has a fully connected subgraph of size s (a clique).

CNF and DNF are conjunctive and disjunctive normal forms, respectively. CNF has the form (x OR (NOT y) OR ... ) AND ((NOT z) OR y OR ... ) AND ..., while DNF has AND and OR exchanged. Any boolean function can be expressed as CNF or DNF, but this might blow up its size exponentially.

The monotone network complexity is the number of binary {AND,OR} gates you need to compute a function. Monotone because increasing the input (setting a bit to 1) never decreases the output. The basic gates have this property, and if you never use NOT the composition has it too. This means that monotone networks can only compute monotone functions. The clique function is monotone, since adding an edge can never destroy an existing clique.

The CNF-DNF-approximators mentioned are a technique for creating a CNF (or DNF) of such a network by introducing a limited amount of errors (hence approximator) at each step. This is done by switching between CNF and DNF at each gate, but discarding parts of the formula that get too large. (I don't really understand how that keeps the error bounded.)

Using the properties of the clique function, it is possible to show that the total number of errors by a limited CNF-approximator must be large, which means that the switching procedure must have been applied many times. This gives a lower bound on the number of gates in any monotone network that computes the clique function, and this bound is exponential.

The paper under discussion attempts to extend this result to non-monotone networks, which can also make use of negation. To do that, it extends the CNF/DNF-switching to also handle negated variables without introducing significantly more errors. (Again, I don't understand how that works.)

Assuming the extension is correct, any bound on the monotone network complexity using CNF-DNF-approximators also holds for the non-monotone network complexity of the given monotone function.

Applying this to the exponential lower bound of the clique function, this means that there is no non-monotone network of a polynomial number of gates that computes it, which implies that there is no polynomial-time Turing machine, which implies P != NP.

This is a bit of a mischaracterization of secure hashing.

You can not uniquely reconstruct a document from a hash value. Indeed, for a typical secure hash function, a given hash value maps to an infinite set of inputs. But because secure hashes are one-way functions, finding any of those inputs for a given output requires brute force. This is why the bidding example works - it's so hard to find any input that hashes to a value that even having one of them is reasonable proof that it was the source document.

*Consider a secure 1024-bit hash function. How many 1025-bit inputs map, on average, to each hash value?

Scott Aaronson has done some really good write-ups about P-NP, including what it means and what avenues of proof are possible. I'd start here: http://www.scottaaronson.com/papers/pnp.pdf. It probably doesn't count as "ELI5", but it's something.

That's a paper worth reading even if you don't understand it all because it will give you a good feeling for the magnitude of the problem. But it's actually surprisingly accessible. Aaronson is quite good at making hard things (relatively) easy to understand.

Here's a great video on the subject: https://www.youtube.com/watch?v=YX40hbAHx3s

Reply on news.ycombinator.com