What exactly does it mean when a problem is NP complete?
In: Mathematics
A problem is NP complete if:
1. It is solvable, even if the method to solving it is no more advanced than “Guess all the possible answers and see what fits”
2. It is easy/fast to check if the problem was solved without going trough the effort of solving it yourself.
3. You can transform the problem in to any other equivalent NP-complete problem.
What the other commenters are saying isn’t *strictly* correct, because they are assuming the solution to a famous unsolved computer science problem: that P is not equal to NP.
The set of P problems are any problems that can be solved quickly
The set of NP problems are problems whose solution can be verified quickly.
It is an open question if these two problems are the same: that if you can verify the solution to something quickly you can also find that solution quickly. While nearly all computer scientists believe that this is *not* the case no proof has been found.
Latest Answers