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