The practical implication of P vs NP problem

Question

Although whether $$ P = NP $$ is important from theoretical computer science point of view, but I fail to see any practical implication of it.

Suppose that we can prove all questions that can be verified in polynomial time have polynomial time solutions, it won't help us in finding the actual solutions. Conversely, if we can prove that $$ P \ne NP,$$ then this doesn't mean that our current NP-hard problems have no polynomial time solutions.

From practical point of view ( practical as in the sense that we can immediately use the solution to real world scenario), it shouldn't bother me whether P vs NP is proved or disproved any more than whether my current problem has a polynomial time solution.

Am I right?

Answer 1

Many of the problems we know to be in NP or NP-complete are problems that we actually want to solve, problems that arise, say, in circuit design or in other industrial design applications. Furthermore, since the diverse NP-complete problems are all polynomial time related to one another, if we should ever learn a feasible means of solving any of them, we would have feasible means for all of them. The result of this would be extraordinary, something like a second industrial revolution. It would be as though we suddenly had a huge permanent increase in computational power, allowing us to solve an enormous array of practical problems heretofore out of our computational reach. The P vs. NP question is important in part because of this tantalizing possibility.

If it were proved that P = NP and the proof provided a specific polynomial time algorithm for an NP-complete problem, then because of the existing reduction proofs, we could immediately produce polynomial time algorithms for all our other favorite NP problems. Of course, a proof may be indirect, and not provide a specific polynomial time algorithm, but you can be sure that if we have a proof of P=NP, then enormous resources will be put into extracting from the proof a speciffic algorithm.

Conversely, if someone were to prove $P \neq NP$, then it would mean that there could be no polynomial time solution for any NP complete problem. (In particular, the last sentence of your second paragraph is not correct.)

Answer 2

Actually $P \ne NP$ does mean that our current NP-hard problems have no polynomials time solutions. NP-complete problems are the hardest problems in NP and NP-hard problems are at least as hard as this. So if $P \ne NP$, then all these NP-hard problems must be harder than P.

Whether the proof helps us find solutions will of course depend on the proof. If $P \ne NP$, then we know not to waste time looking for polynomial solutions.

If $P=NP$, then the real practical benefits would of course come from the solution, rather than the proof. That is fine - there is no reason why all theoretical computer science needs to be directly practical.

Answer 3

Currently, if a manager asks their software engineering team to look at implementing some utility, and the team says that requirements are NP hard, that's a reason that the project requirements need to be changed before work on implementation can begin. That's because no-one knows how to give feasible solutions to such problems.

The plurality of complexity theorists furthermore believe P =/= NP, so that means that there's a widespread belief among experts that feasible solutions to these problems will never be found.

If someone shows P=NP, then if the team says the requirements are NP-complete, then the manager and the team will start to move from talk of theory to possible realisations and their efficiency.

Answer 4

Not directly related to the question, but definitely relevant.

Three days ago proof for P != NP is published. Community thinks it looks serious.

Answer 5

If $P = NP$, computational revolution (once a specific algorithm is identified for an NP-hard problem, with explicit asymptotic runtime bounds).

If $P < NP$ and one can prove it, secure (classical) cryptography provably exists, and a huge missing piece in our understanding of computation is filled in. The first already has significant implications for daily life, and developing the second would have much larger implications.

You should also understand that after 40 years of research, today P=NP carries a host of related ideas like: easy-to-hard phase transition in combinatorial problems; quantifiable boundaries between easy and hard approximate versions of specific NP-complete problems (so getting within 7/8 of the optimal solution is easy but anything closer is NP-complete); counting and randomly sampling combinatorial objects are the same problem; zero-knowledge proofs "that reveal nothing but their own validity" (unforgeable ID cards). It's a very rich universe of ideas and it doesn't run out of questions once you know the answer to P=NP.

Answer 6

There is an interesting heuristic to suggest that P is actually not NP. It is that, roughly, the task of finding out a proof of a statement is an NP task, but that of verifying it is a P task. From our actual experience that verifying a proof is far easier than finding one, we can intuitively expect P != NP to hold true.

The practical application is that a result which would agree with our intuition would be a great thing, and psychologically satisfying moreover.