A search problem is NP-complete if
- It is in Non-deterministic Polynomial Time
- All other problems in NP have a Reduction to it
Therefore, if there is a P algorithm for a problem in NP-complete, we would have an efficient algorithm for every problem in NP.
Hard is classified as NP-Complete, and Easy is classified as in P.
These are the “hardest” problems in the Non-deterministic Polynomial Time class. These problems have two key properties.
- A potential solution can be verified in polynomial time
- They are NP Hard
Many problems do not have an efficient algorithm and in this case, the best known algorithm runs in exponential time relative to its input size. These are classified as “Search Problems”. NP is the class of all well-defined search problems.
Note
Note that P is in NP. NP is a large set that contains P.
Common Problems
- Traveling Salesman Problem
- Knapsack
- SAT
- Graph colouring
- Search Problems
Does or, can all well-defined search problems be solved in Polynomial Time. It is believed that this is not true but no one has proved that this is the case.
Coping with NP Completeness
If a search problem is NP Complete, then a P algorithm is unlikely (unless P = NP). But we can use tricks like: