Explain Like I'm Five

14398 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

[email protected]

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 to c/[email protected]

16 comments fedilink hide all child comments

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 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?"

[–] [email protected] 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.