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

P Subset of NP

Prove that every problem in P is also in NP by constructing trivial certificates and verifiers.

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:

  1. There exists a polynomial-time algorithm A that decides whether an input x belongs to L
  2. To show L is in NP, we need to construct a verifier and certificate system
  3. The certificate? It can be empty (or trivial, like the string "yes")
  4. The verifier V? It simply ignores the certificate and runs algorithm A on input x
  5. Since A runs in polynomial time, so does V
  6. V accepts (x, certificate) if and only if A accepts x

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.