23  P and NP

Modified

February 25, 2026

We now switch gears to discuss the complexity classes P and NP.

Objectives: After learning this material, you should be able to:

23.1 Computational complexity and P

Throughout class, we have asked: how efficiently can you solve a problem? In particular, we often want to know the fastest runtime of any algorithm for a problem such as shortest paths or minimum spanning tree.

Given that, we can also start to classify problems themselves as “easy” (they have a fast algorithm) and “hard” (they have no fast algorithm). We call such classes complexity classes.

More precisely, we’ll look at a very permissive definition of easy: running in polynomial time, i.e. running time \(O(n^k)\) for some constant \(k\). Almost all of the problems we’ve seen in this class fall into this definition, but we’ll see that some care is needed. We’ll also need a universal way to measure running time that works for all problems, whether they’re on graphs, integers, lists, or any other type of input. We’ll do so by measuring the input size in terms of the number of bits needed to write the input down.

Definition 23.1 (Polynomial time) An algorithm is a polynomial-time algorithm if there exists a constant \(k\) such that, when the input is represented using at most \(n\) bits, the running time of the algorithm is at most \(O(n^k)\).

Finally, we’ll make things simpler by focusing on decision problems.

Definition 23.2 (Decision problem) A decision problem is a problem where the answer is either yes or no.

Many problems can be converted into decision problems. For example, the shortest paths problem can be re-framed as a decision problem: is there any path of length at most \(d\)? If we can solve shortest paths in polynomial time, then we can solve the decision problem in polynomial time. And conversely, if we had some polynomial-time algorithm for the decision problem, we could use it to solve the original shortest-paths problem by binary search on \(d\).

Definition 23.3 (\(\mathsf{P}\)) The complexity class \(\mathsf{P}\) consists of all decision problems that have a polynomial-time algorithm.

We tend to think of \(\mathsf{P}\) as problems that are “easy”, or at least “tractable”.

23.2 NP

Now we will look at a broader class of problems. Informally, NP will be the problems where we can “check” or “verify” a yes-answer in polynomial time. An example is the Hamiltonian path problem: given a directed graph, does there exist a path that visits every vertex exactly once? If the answer is yes, then we can ask for such a path and check that it does indeed vist every vertex once. This is easy to check, if we have the path. (In this case, the path itself is called the “witness” that the answer is yes for this given graph.) But it turns out that we don’t know of an efficient (i.e. polynomial-time) algorithm to find such a path.

Definition 23.4 (Verifier) A verifier for a decision problem is an algorithm that satisfies the following properties.

  • The verifier takes as input a pair \((I,W)\) where \(I\) is an instance of the decision problem and \(W\) is the “witness”.
  • The verifier outputs either “accept” or “reject”.
  • The size of the witness satisfies length(W) <= p(length(I)) where \(p\) is some polynomial.
  • If \(I\) is a “yes” instance of the decision problem, then there exists at least one witness \(W\) such that the algorithm accepts \((I,W)\). (“Completeness”)
  • If \(I\) is a “no” instance of the decision problem, there for any witness \(W\), the algorithm rejects \((I,W)\). (“Soundness”)

Example 23.1 (Hamiltonian Path) As mentioned, the Hamiltonian Path decision problem is whether a directed graph has a path that visits every vertex exactly once. It has the following verifier:

  • The witness string is a list of \(n\) of the vertices of the graph.
  • Given \((I,W)\), the verifier checks if \(W\) is a valid path in the graph and if it contains every vertex exactly once.
  • If so, the verifier accepts, otherwise it rejects.

We can see that if there really does exist a Hamiltonian path \(v_1,\dots,v_n\), then for witness \(W = (v_1,\dots,v_n)\), the verifier will accept. On the other hand, suppose there doesn’t exist any Hamiltonian path. In other words, the answer to the problem is “no”. Then no matter what witness \(W\) is provided, the verifier will always reject, because no list of \(n\) vertices can be a valid path that contains every vertex once. So Hamiltonian path has a verifier.

Example 23.2 (Knapsack) The knapsack decision problem is: given a list of objects with weights and values, and given a knapsack size \(W\) and value goal \(V\), does there exist a subset of the items with total weight at most \(W\) and total value at least \(V\)? A verifier is the following:

  • The witness string is a subset of the objects. (This is polynomially-sized, since it is a list of at most \(n\) numbers.)
  • Given \((I,W)\), the verifier adds up the values and weights of the objects.
  • If the total weight is at most \(W\) and the total value is at least \(V\), it accepts. Otherwise, it rejects.

If there really does exist such a subset of items, then that subset is a witness that will cause the verifier to reject. On the other hand, if no such subset exists, then the verifier will reject no matter what witness it is given. This follows because any subset will either have too much weight or not enough value. So knapsack has a verifier.

We can now define the complexity class NP.

Definition 23.5 (\(\mathsf{NP}\)) The complexity class \(\mathsf{NP}\) consists of all decision problems that have a polynomial-time verifier.

We can check that our verifiers for Hamiltonian Path and Knapsack, above, both run in polynomial time. Therefore, both of these problems are in NP.

Exercise 23.1 The Hamiltonian Cycle problem is: given a directed graph \(G\), does there exists a cycle that visits every vertex exactly once, except the start and end vertices? Prove that the Hamiltonian Cycle problem is in NP.

Example solution.

The witness is the cycle that visits every vertex exactly once. The verifier, given the graph \(G\) and a witness string interpreted as a list of vertices, checks that each vertex is in the list once (except the start and end vertex) and checks that the list of vertices is actually a cycle in the graph. If all of these checks pass, it accepts.

This verifier runs in polynomial time, as this is only a linear number of checks (with an adjacency matrix; at most quadratic with an adjacency list). It accepts if and only if the witness is a Hamiltonian Cycle, by definition.

23.2.1 Comparing P and NP

First, we should note that every problem in P is also in NP.

Theorem 23.1 \(\mathsf{P} \subseteq \mathsf{NP}\). That is, any problem that has a polynomial-time algorithm also has a polynomial-time verifier.

Proof. Suppose a problem has a polynomial-time algorithm \(M\). Then the verifier is the following: Given \((I,W)\) where \(I\) is an instance of the problem and \(W\) is a witness, we ignore the witness and just run the algorithm \(M\) on the input \(I\). If \(M\) outputs “yes”, we accept. If it outputs “no”, we reject. This verifier runs in polynomial time. It satisfies completeness because for any yes instance \(I\), regardless of what witness we use, the verifier accepts. It satisfies soundness because for any no instance \(I\), regardless of what witness we use, the verifier rejects.

The largest open problem in Computer Science is whether P and NP are actually the same, i.e. whether P = NP.

Open Problem 1 P = NP

Does \(\mathsf{P}\) equal \(\mathsf{NP}\), or is \(\mathsf{NP}\) a strictly larger set? That is, do there exist problems that have a polynomial-time verifier, but have no polynomial-time algorithm?

It’s worth mentioning that every problem in \(\mathsf{NP}\) can be solved by a brute-force search of the following form:

  • Given an instance \(I\), iterate through all possible witness strings \(W\).
  • For each \(W\), run the verifier to check if it accepts \((I,W)\). If so, return “yes”.
  • If the verifier never accepted, then return “no”.

However, this takes \(\text{poly}(n) 2^{\text{poly}(n)}\) time on inputs of length \(n\). The question of P = NP is the question of whether problems that admit this type of brute-force search can always be sped up to polynomial time.