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

The Class NP (Nondeterministic Polynomial)

Defining NP as problems whose solutions can be verified in polynomial time, introducing the verifier perspective.

The Class NP (Nondeterministic Polynomial)

You'll learn: What NP means and how it's defined through the lens of verifying solutions quickly, rather than finding them.

The Core Idea

While P captures problems we can solve efficiently (in polynomial time), NP captures problems where we can verify a proposed solution efficiently—even if finding that solution might be hard.

Think of it like a jigsaw puzzle: solving the puzzle from scratch might take hours, but checking whether someone else's completed puzzle is correct? That's quick—just verify the pieces fit together properly.

Formal Definition

A language (problem) is in NP if there exists a polynomial-time verifier algorithm V such that:

  • For any input x in the language, there exists a "certificate" (proof/witness) c that convinces V to accept
  • V(x, c) runs in polynomial time relative to |x|
  • If x is not in the language, no certificate can make V accept

The certificate is like a "hint" or "solution candidate" that makes verification easy.

Example: The Subset Sum Problem

Problem: Given a set of numbers and a target, does a subset sum to that target?

  • Finding a subset: potentially requires trying many combinations
  • Verifying a proposed subset: just add the numbers and check—takes polynomial time!

The proposed subset is your certificate. If someone hands you {3, 7, 12} and claims it sums to 22, you can verify this instantly.

The Verifier Perspective

NP stands for "Nondeterministic Polynomial" because a nondeterministic Turing machine could "guess" the certificate and verify it in polynomial time. But practically, we think of NP as the class of problems with polynomial-time verifiable solutions.

Key Takeaway: NP contains problems where solutions can be verified in polynomial time given an appropriate certificate, even if finding that certificate might be difficult.