DEV Community

Fernando Piancastelli
Fernando Piancastelli

Posted on

2 2 2 2 1

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.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay