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”.
Common Problems
- Traveling Salesman Problem
- Knapsack
- SAT
- Graph colouring
- Search Problems