Algorithms and Data Structures · Senior · Question 57 of 75
What does it mean that a problem is NP-complete?
- 1It's proven that no algorithm can solve it
- ✓Correct answer: It's in NP, and every NP problem reduces to it in polynomial time
- 3It can be solved only by a non-deterministic computer
Explanation
Solutions can be checked quickly, but no polynomial algorithm to find them is known. A polynomial algorithm for any NP-complete problem would solve all of NP. Examples: SAT, graph coloring, subset sum.