P Subset of NP
You'll learn: Why every problem solvable in polynomial time (P) is automatically also verifiable in polynomial time (NP).
The Core Relationship
Now that we've defined both P (problems solvable in polynomial time) and NP (problems verifiable in polynomial time with a certificate), we can prove a fundamental relationship: P ⊆ NP. In plain English: every problem we can solve efficiently, we can also verify efficiently.
Why This Makes Sense
Think of it like this: if you can bake a cake from scratch in 30 minutes (solve it quickly), you can certainly taste the finished cake and confirm it's correct in far less time (verify it quickly). The solver can always act as its own verifier.
The Formal Proof
For any problem L in P:
- There exists a polynomial-time algorithm A that decides whether an input
xbelongs toL - To show L is in NP, we need to construct a verifier and certificate system
- The certificate? It can be empty (or trivial, like the string
"yes") - The verifier V? It simply ignores the certificate and runs algorithm A on input
x - Since A runs in polynomial time, so does V
- V accepts
(x, certificate)if and only if A acceptsx
This proves x ∈ L is verifiable in polynomial time, so L ∈ NP.
The Intuition
If you already have a fast solution method, you don't need any extra information (certificate) to verify correctness—just re-solve it! The certificate adds no value when you can already solve the problem efficiently.
Key Takeaway: Every problem in P is also in NP because a polynomial-time solver doubles as a polynomial-time verifier with trivial certificates—simply run the solver itself as the verification procedure.