NP-Completeness

NP-Completeness stems from computational complexity theory. The NP class of problems, which stands for nondeterministic polynomial is the most studied branch of complexity. NP problems are always decision problems, but can be extended to other types of problems by limiting them. When a problem is NP-Complete, it means it is part of the class NP and the class NP-Hard. For any problem that is NP-Complete, verifying a solution is very fast, but finding a solution in the first place is very difficult. In NP-Complete problems, no fast algorithms are known to solve the class of problems, and all the algorithms increase in time taken to solve quickly as the size of the input grows.

A problem, called C, is formally NP-Complete when two conditions are satisfied:

that C be in NP, and
that every other problem in NP is reducible to C in polynomial time.

This means that the problems that are NP complete are those that are both NP-Hard and in NP. It also means that finding a polynomial time solution to any NP-Complete problem is reducible to every other problem that is NP-Complete. This property is what has given rise to the greatest open question in computer science today, whether P=NP. Most computer scientists think that P≠NP, but if it is shown that P=NP, then many very hard problems will have “easy” solutions.

The two possibilities [ Photo credit: Benham Esfahbod ]

BrainMass