Course contentsShow
← Computer Science
Lesson 1892 of 2,87243. Complexity TheoryFree lesson

NP vs P: The Relationship

Understanding that P ⊆ NP and why proving P = NP or P ≠ NP remains the central open question.

NP vs P: The Relationship

What you'll learn: You'll understand why P is contained within NP and why determining whether they're equal is one of computer science's greatest unsolved mysteries.

The Core Relationship

Here's what we know for certain: P ⊆ NP. Every problem solvable in polynomial time (P) is also verifiable in polynomial time (NP). This makes intuitive sense—if you can solve something quickly, you can certainly check a solution quickly.

Think of it like this: If you can complete a jigsaw puzzle in under an hour (solving it), you can definitely verify someone else's completed puzzle in under an hour (just check that pieces fit). The reverse isn't necessarily true though—checking might be much easier than solving from scratch.

The Million-Dollar Question

The central open question is: Does P = NP?

In other words, if we can verify a solution quickly, does that mean we can also find that solution quickly? Most computer scientists believe P ≠ NP—that there exist problems where checking is fundamentally easier than solving—but no one has proven it.

Why It Matters

If P = NP were proven true, it would revolutionize computing. Every problem with easily verifiable solutions would suddenly have efficient algorithms. Cryptography would collapse, optimization problems would become trivial, and drug discovery would accelerate dramatically.

If P ≠ NP is proven, we'd know certain problems are inherently hard, justifying why we've never found efficient solutions despite decades of effort.

Key Takeaway: We know P ⊆ NP with certainty, but whether P = NP or P ≠ NP remains the most famous open problem in theoretical computer science, with profound implications for technology and mathematics.