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
sabbah@lemmy.world
AradFort@lemmy.world
rikudou@lemmings.world
Don_Dickle@lemmy.world
Rikudou_Sage@lemmy.world
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)
submitted 1 week ago by plankton@programming.dev to c/explainlikeimfive@lemmy.world
16 comments fedilink hide all child comments
 
you are viewing a single comment's thread
view the rest of the comments
[โ€“] lime@feddit.nu 5 points 1 week ago* (last edited 1 week ago) (1 children)

Note that only the highest exponent is relevant. With some work we could prove that for example O(n^3 + n^2 + n) is equivalent to O(n^3).

just adding on for others that "some work" can be simply explained as figuring out the answer to "as n grows, which of n^3^, n^2^ or n affects the result the most?"

[โ€“] dfyx@lemmy.helios42.de 4 points 1 week ago

Yes, it's pretty intuitive. A formal proof is still a bit more work than what I can fit in an ELI5 but at the same time simple enough that it can be given to a 2nd semester computer science student as an exercise.