97
ELI5 how P, NP, NP-Complete, and NP-Hard work? If you have a video you'd recommend that works too
(files.catbox.moe)
this post was submitted on 10 Dec 2024
97 points (91.5% liked)
Explain Like I'm Five
14389 readers
1 users here now
Simplifying Complexity, One Answer at a Time!
Rules
- Be respectful and inclusive.
- No harassment, hate speech, or trolling.
- Engage in constructive discussions.
- Share relevant content.
- Follow guidelines and moderators' instructions.
- Use appropriate language and tone.
- Report violations.
- Foster a continuous learning environment.
founded 2 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
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