I know what an np complete problem is and the procedure to prove it but why do we have to prove a problem is NP complete or NP hard? What was the need to define this whole new class?
I am not 100% certain, but I can speculate. The idea is that with SAT you could basically model a ND Turing Machine which would solve an NP problem if and only if there was a SAT solution. Proving things in general for NP is complicated, so I can imagine that people who noticed the strength of SAT saw it as a stepping stone toward P=NP (or !=, for that matter). Ultimately, taking this to its logical conclusion, anything that can be polynomial-time-reducible to SAT was special, and the focus would just have to be on finding a poly-time solution to SAT.
I think that the need to classify problems as NP complete/hard lies in the kind of approach that you take when dealing with them.
For example, the traveling agent's problem could be solved by a laptop computer given enough time, but this time would probably (depending on the size of the problem) be too much, not necessarily because the amount of data is very large, but because of the complexity of all currently known deterministic solutions to the problem. Once a problem is labeled as NP complete, you'd need to take a different approach to it, for example non-deterministic solutions. The issue with these kind of solutions is that you won't necessarily find the *best* possible answer to the problem, but you can find a good answer in an acceptable amount of time (polynomial).
Researchers believe NP-complete (decision problems) and NP-hard (optimization problems) are intractable. If you can show your problem of interest is NP-hard, then you have eluded to the computational difficulty for solving that problem. Problems such as SAT are widely believed to be very difficult to solve in polynomial time with respect to the input size.
Why is proving a problem is NP-hard or a decision problem is NP-complete important? There are many reasons (here are 3):
1. If you find a polynomial-time algorithm for a given NP-hard problem, then any problem that you derived your result from can also be solved in polynomial time. For example, if I found a polynomial-time algorithm for the makespan problem on identical parallel machines (when number of machines m=2), then I can also solve the partition problem in polynomial-time. These reductions can be traced right down to the root. Why? In polynomial time I can turn any partition problem instance into a scheduling instance in polynomial time. That's why these reductions are useful (among many other reasons). It means "it is at least as hard". It is worth noting that NP-hard isn't the same as NP-complete. There are problems that are NP-hard, but not NP-complete. For example, the Halting Problem is NP-hard, but not NP-complete (because it is not in NP). There are other interesting implications you can draw from polynomial-time reductions.
2. It gives us the ability to categorize problems. We normally don't talk about algorithms then problems, we talk about algorithms with respect to problems. This is just another class among many others. This is a big part of Computational Complexity Theory.
3. Gives motivation to study approximation algorithms. Solving for exact optimal solutions can be very costly. Using approximation algorithms give polynomial-time time complexity, and an approximate feasible solution. It introduces the idea of hardness of approximation as well, which introduces a whole other realm of the P vs. NP problem where the existence of certain types of approximation algorithms could imply P=NP.
Hope this helps!
Plain English explanation in the intro part of Garey & Johnson (1979), and the cartoon there, provide as simple a motivation as one can hope to give. Three and a half decades later, their book still sets the bar -- including on why would one bother studying computational complexity in general, and why proving some problems are NP-complete, in particular.
NP by definition includes P and many smaller classes. So if you know that a problem is in NP, this only gives you an upper bound on its complexity. But it might be very simple. Proving NP-completeness shows that the problem is among the hardest ones in the class NP.
NP-complete (and NP-hard) problems are a very natural class - they are the problems that are "equally as difficult" ("at least as difficult") as, say, SAT. As others have pointed out, this class of problems can be seen as the "hardest" problems in NP (so they will not be in P if P!=NP but finding a polynomial-time algorithm for them will show P=NP) but what I find fascinating about this is that NP-complete problems even exist! There is no reason to expect /every/ problem in NP to reduce to one particular problem in NP, but not only is that the case, but there are a whole class of problems for which this is true.
Right Paul, it is to some extent fascinating that a class of hardest problems exists (instead of numerous "maxima"). And what is more: it is not just an abstract concept; rather there are incredibly many concrete problems from all kinds of areas that show how relevant this class in terms of applications to real world questions,
- Badges
- Science topic