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
Common Problems
- Traveling salesman problem
- Knapsack
- SAT
- Graph colouring