15
$\begingroup$

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?

  • 1
    Have you read ["What are np-complete problems and why are they so important?"](http://math.stackexchange.com/questions/726/what-are-np-complete-problems-and-why-are-they-so-important)2010-08-09
  • 0
    @Casebash, I read. But my point is precisely that even if we can prove that `P=NP` it won't help me find an efficient algorithm for travelling salesman problem.2010-08-09
  • 0
    For an amusing discussion of these issues, I recommend http://www.scottaaronson.com/blog/?p=1222010-08-09
  • 4
    *"..this doesn't mean that our current NP-hard problems have no polynomial time solutions."* - [Yes it does.](http://en.wikipedia.org/wiki/NP-hard)2010-08-09

6 Answers 6

17

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

  • 4
    There is an explicit polynomial time algorithm which, if P equaled NP, would solve NP-complete problems in poly-time. See Theorem 2 in http://scottaaronson.com/blog/?p=392 . Of course, it is likely that a proof of P=NP would provide a much better algorithm than this.2010-08-09
  • 0
    Oops, got that slightly backwards. What is known is that this algorithm does solve SAT; what would follow from P=NP is that this algorithm is in P.2010-08-09
  • 0
    This is well and good, and shows why a proof of P=NP would change the world, but it doesn't answer the following question: Given that we already "know" P≠NP (it seems a widely held consensus among computer scientists), what would be the practical implications of a proof of this already-believed-to-be-true conjecture? (This may not have been the question originally asked, though.)2010-08-09
  • 1
    @ShreevatsaR , I think I can answer your question. If P≠NP then for NP complete problem ( such as subset sum problem) there would never be any polynomial time solution.2010-08-09
  • 0
    @Ngu: I know the significance of P≠NP; I was asking about the significance of a *proof* of it. To answer my own question as best as I can: any proof would likely involve new insights about computation, research could move in new directions, etc. The consequences are to research, mainly, not immediately to practice (somewhat similar to "practical consequences of proof of Fermat's Last Theorem").2010-08-09
  • 0
    ShreevatsaR's question is addressed in my answer. Knowing P=NP (maybe even without proof) is world-changing once you have an explicit algorithm for an NP-hard problem, but not without that. Knowing P < NP is world-changing once you have a proof, but not otherwise, because (a) the proof is a security or correctness proof for algorithms in cryptography and elsewhere, and (b) having powerful enough methods to demonstrate a dividing line between easy and hard problems implies an incredible advance in methods that would lead to theoretical and applied breakthroughs across the board in CS.2010-08-10
  • 0
    It's worth emphasizing that polynomial time algorithms aren't necessarily practical. For example, the AKS primality test has had zero impact on practical primality testing. Generally the polynomial degree and constants may be so huge that such results could prove to be only be of theoretical (asymptotic) value.2010-09-20
8

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.

  • 1
    BTW, cryptography doesn't commonly use NP-hard problems. It relies on the hardness of factoring, discrete log, etc., which are already believed not to be NP-hard. (I think this is because for cryptography we need average-case hardness, and such a property is not known for any NP-complete problem.)2010-08-12
  • 0
    There are notions of average-case NP completeness but only a few problems are known to satisfy it. I think Levin showed completeness for some tiling problems and Ajtai showed that an NP problem on shortest vectors in a lattice has almost all cases as hard as the worst case. Theoretical cryptography uses one-way functions or other assumptions that are slightly stronger than P < NP, practical cryptosystems use problems that are not considered NP-complete (in part from the need for efficiency).2010-08-12
5

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.

  • 1
    *"NP-hard problems are the hardest problems in P and if there are problems not in P, they must be harder than P."* - Er, no. **NP-Complete** problems are the hardest problems in **NP**; **NP-hard** problems are *at least* as hard as NP-Complete problems (but might not be in NP at all) - if $P \neq NP$, then **no** NP-Hard problems are in P.2010-08-09
  • 0
    @BlueRaja: Oops, my bad2010-08-09
3

Not directly related to the question, but definitely relevant.

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

  • 0
    Yup, I saw that link and it was what prompted me to ask this question.2010-08-10
  • 0
    Terry Tao and several others have said they think Deolalikar's proof is wrong, sadly :(2010-08-13
  • 0
    @Katie: Maybe it's not that bad, then there's still hope for P = NP :)2010-08-14
1

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.

1

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.

  • 0
    The set of theorems is not NP, since the witnessing object, the proof, can be and often is much larger than the original query, the purported theorem. In particular, if being a theorem were an NP problem, then it would be decidable (in exponential time), but this is known not to be true. For example, if one could decide whether or not something was a theorem, even in exponential time, then one could solve the halting problem, since program $p$ halts on input $n$ if and only if this is provable in PA.2010-08-10