# Why is it important to prove that a problem is NP-complete?

Am I correct in understanding that proving a problem NP complete is a research success? If so why?

Ali, good question.

Suppose you want to show that some problem P is computationally hard. Now, you could conjecture that P is hard just based on the fact that we don't have any efficient algorithms for it yet. But this is rather flimsy evidence, no? It could be that we have missed some nice way to look at P which would make it very easy to solve. So, in order to conjecture that P is hard, we would want to accumulate more evidence. Reductions provide a tool to do exactly that! If we can reduce some other natural problem Q to P, then we have shown P is at least as hard as Q. But Q could be a problem from some completely different area of mathematics, and people may have struggled for decades to solve Q also. Thus, we can view our failure to find an efficient algorithm for Q to be evidence that P is hard. If we have lots of such Q's from many different problem domains, then we have a huge body of evidence that P is hard.

This is exactly what the theory of NP-completeness provides. If you prove your problem to be NP-complete, then you have tied its hardness to the hardness of hundreds of other problems, each of significant interest to various communities. Thus, morally speaking, you can be assured that your problem is indeed hard.

• So the initial aim is to find an efficient algorithm for P but since that appears unachievable one assumes that P is computationally hard and then your answers explains the rest? – Ali Dec 5 '10 at 11:35
• We want to show that our problem P is computationally hard, but we don't want to assume that P is hard to prove that P is hard :) Instead, if you prove P to be NP-complete (or even NP-hard but let's ignore the distinction here), you've shown that if any one out of hundreds of already-well-scrutinized problems is hard, then P is also hard. This is because if there were an efficient algorithm for P, there would also be efficient algorithms for each of the hundreds of problems. – arnab Dec 5 '10 at 17:15
• @Ali: I strongly suggest you look at an introductory complexity theory textbook. This website is not really a forum for such questions, but more for research-level questions. – arnab Dec 5 '10 at 17:16
• @Ali: I definitely recommend you to read Garey and Johnson. The famous cartoon in the book is a must-see! – Tsuyoshi Ito Dec 6 '10 at 2:58

Proving a problem NP-Complete is a research success because it frees you from having to search for an efficient and exact solution for the general problem you are studying. It proves that your problem is a member of a class of problems so difficult that nobody has been able to find an efficient and exact algorithm for any of the problems, and such a solution for any of the problems would imply a solution for all of the problems.

It is usually a stepping stone, because your problem is still there - you simply have to relax your requirements. Usually people try and figure out how to relax one or more of "efficient", "exact", or "general". Inefficient-and-exact-and-general is the attempt to find better and better constants in the exponent for these algorithms. Efficient-and-inexact-and-general is the study of approximation algorithms. Efficient-and-exact-but-not-general is the study of fixed-parameter tractability and the search for subclasses of input for which efficient algorithms can be found.

• Nice point for three ways to relax the problem! I guess randomized algorithms falls in the "efficient-and-inexact-and-general" category. – Hsien-Chih Chang 張顯之 Dec 8 '10 at 2:48
• Really? Not all randomized algorithms are inexact. – Jeffε Dec 8 '10 at 4:21
• And of course you are right, JeffE. Also, I understand you are (or were) instructing a former student of mine in algorithms! As to Hsien-Chih's point, I don't think randomized algorithms fit well in this scheme. Certainly some randomized algorithms (genetic algorithms and neural nets come to mind) are inexact yet efficient and general, but some randomized algorithms are quite exact - consider the algorithm for verifying a number is prime! It's a random algorithm, but I am quite confident that nobody has ever gotten a non-prime out of any reasonable implementation. – Peter Boothe Dec 8 '10 at 18:27

Let's see two different cases why two different persons would like to prove a problem $NP-complete$:

a) You are working on a software project. Having specified your system , you are starting to define the architecture of your application. This includes breaking down the large problem/need the application serves to smaller problems. Let's say that you have been given the task to find an efficient (we don't want our application to be slow!) algorithm for one of those smaller problems. After struggling for some time, you cannot find a polynomial algorithm. Then you might think: maybe this problem is very hard, so it's very difficult (or even impossible) to find an efficient algorithm. By proving that the problem is $NP-complete$, you have some evidence for this conjecture of yours and you should start considering an alternative approach (e.g. altering the problem so it becomes easier).

b) You are researching complexity theory. By definition, you want to characterize problems (or classes of problems) according to the number of resources needed , i.e. the difficulty to solve them. By proving that a certain problem is $NP-complete$, you gain some insights:

i) You know have a vast knowledge of the problem. Instead of working on a single problem, you can work with the class of $NP-complete$ problems, which might lead you to new insights.

ii) You allow researches that want to prove $P=NP$ another way to do that. Maybe your problem is easier to attack than $3-SAT$.

iii) On the reverse direction, you can use your new problem as a representative of $NP-complete$ problems. By studying it, you can perhaps understand why this problem is so difficult to solve (= does not have an efficient algorithm) and apply this knowledge to all other problems in the class. (that's what Deolalikar tried to do with the $CLIQUE$ problem)

Summarizing, characterizing a problem allows you to use common techniques. By studying the class it is related to, you can think in an abstract level, without bothering about the specifics of this particular problem, which is common in mathematics and science in general. Working with classes instead of individual members allows you to use known techniques and furthermore, apply your insights to a larger number of objects, instead of only one.

• Many people solve NP-complete problems in practice, even if they're NP-hard to approximate. In the average case many problems turn out to be much easier, although this can be hard to show; it is even harder to prove anything about heuristic algorithms that work well in practice. I suggest the software architect to ask someone whether the problem is "really" difficult before giving up and changing her design. – Yuval Filmus Dec 8 '10 at 5:51
• I am not saying that the design needs to change. Using a heuristic or approximation algorithm seems to me (falsely?) like changing the problem... since know you are asking for less precise solutions (are those acceptable? it depends on the application!). – chazisop Dec 8 '10 at 11:08

Each problem has several connections with other problems. In addition, there are relations between a problem and complexity classes.

Therefore, classifying one problem as NPC usually gives us insight into other problems, as well as complexity classes.

For instance, take the graph isomorphism (GI) problem. In the following paper:

Uwe Schöning, Graph isomorphism is in the low hierarchy, Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124; also: Journal of Computer and System Sciences, vol. 37 (1988), 312–323.

it is proven that if GI ∈ NPC, then the polynomial hierarchy (PH) collapses to its second level; which will be a major breakthrough in structural complexity theory.

I see that previous answers explain why it is important to know if a problem is or is not NP-complete, but none seems to directly address the question: The proof of "$p$ is NP-complete" is not considered a research success for all $p$. It depends on various things, such as whether $p$ is interesting, whether the proof has new techniques, whether "$p$ is NP-complete" has interesting consequences, etc.

• I've heard that there was a time when you proved some problems are NP-complete, you would have your PhD thesis. Is that true? – Hsien-Chih Chang 張顯之 Dec 9 '10 at 11:57
• @Hsien-ChihChang張顯之: I can't comment on that, but those results certainly used to be much more popular a few decades ago. It seems increasingly difficult these days to publish a paper in which you "only" prove a hardness result (with the exception of "famous problems" of course), whereas that would not have been a problem in the 70's-80's, judging from the abundance of this kind of papers during that period. – Anthony Labarre Jan 4 '12 at 14:55