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
I had a huge reply, but after some googling to try and understand, I'm gonna go with this wiki image:
https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/1024px-P_np_np-complete_np-hard.svg.png
(Black graph on transparent background, this might be better: https://en.m.wikipedia.org/wiki/NP_(complexity)#/media/File%3AP_np_np-complete_np-hard.svg )
I see it as:
P: is a problem that gets solved and proved easily.
Np: is is a problem that is difficult to solve but easy to prove.
P=np ie np-complete: as difficult to solve as it is to prove.
Np-hard: no single solution, might require multiple "np" solutions (eg a different algorithm for each input element)
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.