Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 59 ยท Complexity

Nondeterminism and the Class NP

Learn what NP means with two equivalent views, nondeterministic machines and polynomial-time verifiers, then check certificates for Subset Sum and Hamiltonian paths in Python.

Some problems are easy to check but seem hard to solve. Give someone a filled-in Sudoku and they can confirm it in seconds. Ask them to find the solution from scratch on a huge board and the best known methods blow up. Another example: if I claim that 1,000,001 is composite and tell you "it is divisible by 101", you can verify my claim with one division. Finding such a factor in the first place is the hard part.

The class NP captures exactly this gap between checking and finding. It is the most famous class in computer science because of one open question: is every problem whose solutions are easy to check also easy to solve? This lesson defines NP in its two standard ways and shows they are the same.

NP as "nondeterministic polynomial time"

A nondeterministic Turing machine (NTM) may have several possible moves from a configuration. It accepts an input if at least one branch of its computation ends in the accept state. Its running time on an input is the length of the longest branch.

TEXT
NTIME(t(n)) = { L : some NTM decides L, and every branch halts within O(t(n)) steps }
NP = NTIME(n) โˆช NTIME(n^2) โˆช NTIME(n^3) โˆช ... = โ‹ƒ_k NTIME(n^k)

NP stands for Nondeterministic Polynomial time. It does not mean "not polynomial". Every problem in P is also in NP, because a deterministic machine is just a nondeterministic machine that never has a choice.

Think of an NTM as a machine that guesses and then checks. It writes down a guess in polynomial time (by making a nondeterministic choice at each cell), then runs an ordinary deterministic check on the guess. If any guess passes, the input is accepted.

flowchart TD
    S["Input w"] --> G["Guess a certificate c<br/>(polynomial length, nondeterministic)"]
    G --> V["Verify (w, c)<br/>deterministic, polynomial time"]
    V -->|"some c passes"| A["Accept"]
    V -->|"every c fails"| R["Reject"]

A nondeterministic machine guesses a certificate and checks it. One passing branch is enough to accept.

NP as "efficiently verifiable"

The second definition never mentions nondeterminism. A verifier for a language L is a deterministic algorithm V such that

TEXT
w โˆˆ L  โ‡”  there is a string c with |c| โ‰ค p(|w|) for which V(w, c) accepts

The string c is a certificate (or witness, or proof). V must run in time polynomial in |w| alone, which is why the certificate cannot be longer than a polynomial: V would not even have time to read it. Then NP is the class of languages that have a polynomial-time verifier.

The two definitions agree. Given a verifier, an NTM guesses c and runs V. Given an NTM, take the sequence of nondeterministic choices on an accepting branch as the certificate, and let V replay those choices deterministically. Both definitions say "yes-instances have short, quickly checkable proofs". Note the asymmetry: for a no-instance there is nothing to check, because no certificate exists.

Classic problems in NP

Problem Instance Certificate
SUBSET-SUM numbers and a target t the chosen subset
HAMPATH directed graph, nodes s and t the path itself
COMPOSITES integer N a nontrivial divisor
CLIQUE graph and number k the k vertices
SAT boolean formula a satisfying assignment
VERTEX-COVER graph and number k the k chosen vertices

Let us make the verifier idea concrete. Below, the verifier for SUBSET-SUM is a one-liner and runs in time linear in the input, while the only generic way to find a subset is to try all 2^n of them.

Python Verifying versus searching for Subset Sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Checking one certificate costs a few operations. Proving that no subset works forces the search through all 2^n candidates (the loop above tries 64, 1,024, 16,384 and 262,144 of them). That asymmetry is the heart of NP.

A nondeterministic machine, simulated

You cannot build a real nondeterministic machine, but a deterministic program can simulate one by exploring every branch. This is exactly why NP is believed to be harder than P: the simulation can take exponential time, because there may be exponentially many branches.

Python Simulating guess-and-check for COMPOSITES

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For composites the first accepting branch appears early (the smallest factor), but for a prime we must visit every branch before we can reject. A deterministic simulation of an NTM that runs in time t(n) takes at most 2^O(t(n)) steps, which gives the first known containment:

TEXT
P โІ NP โІ EXPTIME

Nobody has proved that either inclusion is strict. We know only that P โ‰  EXPTIME (the hierarchy theorem, covered later in this chapter), so at least one of the two inclusions must be a real gap.

Worked example: showing a problem is in NP

To prove that a language belongs to NP you do two things: say what the certificate is, and describe a polynomial-time check. Take HAMPATH.

  1. Certificate: a list of the nodes in the claimed path, v1, v2, ..., vn. Its length is n, polynomial in the graph size.
  2. Verifier: check that the list contains each node exactly once, that v1 = s and vn = t, and that each consecutive pair is an edge. All of this takes at most O(n^2) steps.
Python Polynomial-time verifier for Hamiltonian paths

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Do not argue that a problem is in NP by saying "it is hard, so it must be NP". NP is about the existence of a short certificate with a fast check. A problem can be hard (undecidable, or needing exponential space) without having any such certificate.

What about the complement?

The verifier definition is lopsided: it certifies yes-answers. The class coNP holds the languages whose complement is in NP, in other words, problems where no-answers have short certificates. For example, "is this formula unsatisfiable?" and "is this graph free of a Hamiltonian path?" are natural coNP problems. It is not known whether NP = coNP. P is closed under complement, so P โІ NP โˆฉ coNP; whether the containment is strict is open too.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the N in NP stand for?

    NP is nondeterministic polynomial time: the class decided by nondeterministic Turing machines running in polynomial time.
  2. 2. Which statement defines a polynomial-time verifier?

    A verifier takes the input and a polynomial-length certificate, runs in polynomial time, and accepts for some certificate exactly when w is in L.
  3. 3. How is P related to NP?

    A deterministic machine is a special case of a nondeterministic one, so P is contained in NP. Whether the inclusion is strict is the open P versus NP problem.
  4. 4. A deterministic simulation of a nondeterministic machine that runs in time t(n) takes about

    The simulation may have to try every branch, and there can be exponentially many branches in the running time.
  5. 5. Which problem is naturally in coNP rather than obviously in NP?

    Unsatisfiability is the complement of SAT. A no-answer to SAT (no satisfying assignment) has no obvious short certificate.

Summary

  • NP is the class of languages decided by nondeterministic machines in polynomial time.
  • Equivalently, NP is the class of languages with a polynomial-time verifier and polynomial-length certificates.
  • To place a problem in NP, name the certificate and give a polynomial-time check.
  • P โІ NP โІ EXPTIME; whether P equals NP is open.
  • coNP collects problems whose no-answers have short certificates.

Next: Polynomial-Time Reductions