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

Verification vs Solution

Distinguishing between finding a solution and verifying a proposed solution in polynomial time.

Verification vs Solution

What you'll learn: You'll understand the crucial difference between finding a solution to a problem and checking whether a proposed solution is correct — and why this distinction matters for complexity theory.

The Core Distinction

Imagine you're solving a massive jigsaw puzzle. Finding the solution means starting from scattered pieces and figuring out how they all fit together — that could take days. But if someone hands you a completed puzzle and asks "Is this correct?", you can verify it much faster by checking that adjacent pieces match and all pieces are used.

In computational complexity, this same divide exists:

  • Solving (or finding a solution): Given a problem instance, compute a valid solution from scratch
  • Verifying (or checking a certificate): Given a problem instance and a proposed solution, check whether that solution is correct

Why This Matters for NP

The class NP is defined around verification, not solution. A problem is in NP if:

  • Finding a solution might be hard (we don't know)
  • But verifying a proposed solution can be done in polynomial time

For example, consider the Hamiltonian Path problem (does a graph contain a path visiting each vertex exactly once?):

  • Solving: Searching through all possible paths — potentially exponential time
  • Verifying: Given a proposed path, check it visits each vertex once — polynomial time (just walk the path and mark vertices)

This asymmetry is fundamental: verification being easy doesn't tell us that finding the solution is easy.

The Certificate

The proposed solution being verified is called a certificate or witness. For NP problems, there exists a polynomial-time verifier that can check certificates efficiently, even when generating them seems intractable.

Key Takeaway: The essence of NP is that solutions can be verified quickly even when finding them may be exponentially hard — this verification-vs-solution gap is what makes NP distinct from P and central to computational complexity.