Some computing problems are “easy”* to solve. We call these P.
Some problems let us easily check a proposed solution if we’re given one. We call these NP.
All problems in P are also in NP, since checking a solution proposal works is never harder than solving the problem starting from nothing.
We suspect but can’t prove that some problems in NP are not in P.
It turns out that it’s possible to translate any problem in NP into the boolean satisfiability problem (SAT) using an easy algorithm, so this problem effectively is an upper bound on how hard it could be to solve problems in NP - we could always translate them into SAT and solve that instead if that sequence is easier.
We call SAT, and any problem that it can be translated into easily in the same way, the problem class NP-hard.
NP-complete is just those NP-hard problems which are also in NP, which is many but not all of them.
Some computing problems are “easy”* to solve. We call these P.
Some problems let us easily check a proposed solution if we’re given one. We call these NP.
All problems in P are also in NP, since checking a solution proposal works is never harder than solving the problem starting from nothing.
We suspect but can’t prove that some problems in NP are not in P.
It turns out that it’s possible to translate any problem in NP into the boolean satisfiability problem (SAT) using an easy algorithm, so this problem effectively is an upper bound on how hard it could be to solve problems in NP - we could always translate them into SAT and solve that instead if that sequence is easier.
We call SAT, and any problem that it can be translated into easily in the same way, the problem class NP-hard.
NP-complete is just those NP-hard problems which are also in NP, which is many but not all of them.
*: require asymptotically polynomial running time