What exactly does it mean when a problem is NP complete?
In: Mathematics
It means the problem is both NP and NP-Hard.
Here’s the breakdown:
There are P problems. These are decision problems (yes/no answer problems) where the solution can be found quickly.
There are NP problems, which are decision problems where a solution can be *verified* quickly. E.g. if I give you a Sudoku puzzle solution, you can quickly check if I’m right or not. P problems are also in NP because if you want to verify an answer to a P problem, you can just quickly find the solution yourself and compare them.
There are NP-Hard problems. Every problem in NP can be reduced to an NP-Hard problem. NP-Hard problems do not need to be decision problems and they do not need to be verified quickly. If you can solve an NP-Hard problem quickly, you can solve all NP problems quickly.
And then there are NP-Hard problems that are also in NP. These are called NP-Complete problems. These are kind of special because it means there are NP problems that can be reduced to other NP problems. And if you can solve any NP-Complete problem quickly, then you can solve all NP problems quickly.
Latest Answers