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
The diagram is pretty good but your interpretation is not quite right, especially for NP-complete and NP-hard.
NP-hard means "at least as hard as all problems in NP", proven by the fact that any single NP-hard problem can be used to solve the entire class of all NP problems.
NP-complete means "at least as hard as all problems in NP and itself also in NP", so the intersection between NP and NP-hard.
The thing about P = NP or P != NP is something different. We don't know if P and NP are the same thing or not, we don't have a proof in either direction. We only know that P is at least a subset of NP. If we could find a P solution for any NP-hard problem, we would know that P = NP. That would have massive consequences for cryptography and cyber-security because modern encryption relies on the assumption that encrypting something with a key (P) is easier than guessing the key (NP).
On the other hand, at some point we might find a mathematical proof that we can never find a P solution to an NP-hard problem which would make P != NP. Proving that something doesn't exist is usually extremely hard and there is the option that even though P != NP we will never be able to prove it and are left to wonder for all eternity.