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

  1. Be respectful and inclusive.
  2. No harassment, hate speech, or trolling.
  3. Engage in constructive discussions.
  4. Share relevant content.
  5. Follow guidelines and moderators' instructions.
  6. Use appropriate language and tone.
  7. Report violations.
  8. Foster a continuous learning environment.

founded 2 years ago
MODERATORS
 
you are viewing a single comment's thread
view the rest of the comments
[–] dfyx@lemmy.helios42.de 4 points 1 week ago* (last edited 1 week ago)

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.