98
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 month 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 6 points 1 month ago* (last edited 1 month ago)

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 5 points 1 month 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.

this post was submitted on 10 Dec 2024
98 points (92.2% liked)

Explain Like I'm Five

14648 readers
3 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