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
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
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
One important addendum: complexity classes always consider how hard a problem is depending on the input size. Sorting is in P (usually
O(n*log(n)), so one of the easiest problems overall) but given a few trillion inputs, it would be pretty much impossible to solve on consumer hardware. On the other hand, problems like 3-sat, the knapsack problem or travelling salesman are all NP-hard but with small enough inputs (up to a few dozen or so), they are easy to solve, even with pen and paper and are even regularly included in puzzle books.