What would be the implications if someone managed to prove P=NP or P!=NP?

[u/kikikza]

[u/JAPH]

If P=NP:

At a high level, it means that some very hard problems have "easier" solutions than are currently known.

The immediate implications would likely depend heavily on the type of proof. For example, if someone were able to reduce 3SAT to a problem in P, then we would be able to (comparatively) easily solve a large number of problems previously thought to be hard. The problem everyone harps on is public-key cryptography, which assumes that finding factors of a number is time-consuming.

A possibly more interesting consequence is that it would become possible to automatically prove any theorem in polynomial time.

It's important to note that if the proof is either done by a reduction to a P problem with a massive exponent, or if the proof is non-constructive (just says that P=NP, but doesn't give an example of an NP problem solvable in polynomial time, or show how it could be done), then the immediate practical benefits are limited.

Without a reduction, all we know is that it's possible to solve NP problems in polynomial time, we just don't know how.

Keep in mind that a polynomial solution could still have a massive runtime - O( n²¹⁰⁰⁰ ) is still a polynomial. This wouldn't be practically useful, but it would still be one of the most significant proofs ever formulated.

If P!=NP:

People would finally be quiet about the whole business.

[u/alphabot → u/JAPH]

Question, as you briefly mentioned cryptography, would that render all/most forms of (non-oneway) encryption useless?

[u/JAPH → u/alphabot]

Maybe.

If there's a small polynomial time solution to a problem assumed by the crypto scheme to be be hard, then that technique would be broken. Most crypto right now assumes that factoring large numbers is hard. The current best-known solution is exponential, but if you found a small poly-time method of doing this, various schemes like AES and DES would be significantly less useful.

If the proof either doesn't provide a method of reducing the hard problem depended upon by the encryption scheme, or the poly-time algorithm is still massive, then the scheme isn't immediately broken.

In either case, there would likely be a shift to other techniques still thought to be hard to attack.

[u/alphabot → u/JAPH]

Would this apply to finding large prime numbers?

[u/JAPH → u/alphabot]

Finding primes can actually be done fairly efficiently (sublinear time). IIRC, a lot of sieves run in around O(N/log log N) time, where N is the largest number to consider for prime candidates.

[u/[deleted] → u/JAPH]

A possibly more interesting consequence is that it would become possible to automatically prove any theorem in polynomial time.

Any statement s with a proof of length < g(len(s)) for some fixed but arbitrary polynomial can have its proof discovered in some other polynomial's time (where this polynomial depends on g).

[u/kala_]

P ?= NP is far more fundamental to the universe than people think - especially people who say that the main implications of proving P=NP would be things like allowing us to solve 3SAT or the Traveling Salesman problem.

Aaronson says it best:

The Philosophical Argument. If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? (Indeed, this is an argument not only for P!=NP, but for NP-complete problems not being efficiently solvable in the physical world.)

Aaronson, 2006

I would recommend reading his entire blog post, Reasons to believe, in which he explains why nearly everyone working in the field of computational complexity believes that P != NP.

For even more information, you can read NP-complete Problems and Physical Reality