ELI5: What is the P vs NP problem?
Imagine you have a giant box of Lego bricks.
"P" problems are like building a specific Lego creation with instructions. If you have the instructions, you can build it step-by-step, and it's relatively easy and fast. You know you can finish it in a reasonable time.
"NP" problems are like being given a finished Lego creation and being asked: "Can this be built with the bricks in that box?". You can't see the instructions. You might not even know if instructions exist! To be sure, you might have to try every possible combination of bricks. This could take a very, very long time - maybe longer than you have.
But, if someone shows you a video of how they built it (the "proof" or "solution"), you can quickly watch it and see that it's possible. Verifying the solution is fast and easy.
The big question of P vs NP is: If you can easily verify a solution to a problem, can you also find that solution easily and quickly?
In other words, are P and NP the same? Does every problem that's easy to check (NP) also have an easy way to be solved (P)?
Most experts think that P is not equal to NP. They believe that some problems are genuinely harder to solve than to verify. But nobody has been able to prove it yet. If someone proves that P=NP, it would change the world. It would mean that many hard problems, like breaking codes, finding cures for diseases, and creating amazing new things, could be solved much faster.
