DEV Community

Fernando Piancastelli
Fernando Piancastelli

Posted on

P=NP? 256 chars

This is a submission for DEV Computer Science Challenge v24.06.12: One Byte Explainer.

Explainer

If a problem has an answer which can be quickly checked for correctness, does it mean the problem must have a solution that can be calculated quickly as well (P=NP)? Or just because we can quickly check an answer does not mean it is easy to get one (P≠NP)?

Additional Context

This is arguably the hardest, most famous and difficult open problem (no general proof exists yet) in Computer Science and even for general Math. So of course I'd take a crack at describing it at this challenge!

Since this is tagged as a #beginners challenge I tried to do come up with an answer that might not be 100% formal math because I didn't want to rely on the reader knowing that "quickly" here means "in polynomial time" or what a P and NP-problem actually is, so a reader not familiar with the topic might at least get a good grasp of what the problem is about. Just know that many researchers dedicate their entire careers studying this problem, so enunciation alone is a worthy topic in itself.

It is believed that P≠NP because there's more evidence pointing to it than the alternative: cryptography as we know rely heavily on P≠NP being true; if proven not to be the case a whole new paradigm of computing could come to light and break stuff we consider secure to use.

Top comments (0)