P and NP

The most important question of them all is not “Why is there something instead of nothing?” but rather “Is P = NP?”

Watch First



As always, when we say “polynomial time” without qualification, we mean polynomial in the number of bits in which the problem input is encoded.

Exercise: Prove that all functions in P are also in NP.


The following problems are all in NP.

Given weighted graph $G$, nodes $s$ and $t$ in $G$, and value $k$, is there a path $p$ from $s$ to $t$ such that $weight(p) \leq k$?
Given complete weighted graph $G$ and value $k$, is there a Hamilton cycle $c$ visiting every node in $G$ such that $weight(c) \leq k$?
Given weighted graph $G$ and value $k$, is there a spanning tree $t$ such that $weight(t) \leq k$?
Given graph $G$ and value $k$, is there a vertex cover $s$ for $G$ such that $|s| \leq k$?

These are in NP because we can check in polynomial time

Exercise: Argue why these are all polynomial-time checkable.
Exercise: Two of the above problems are currently known to be in P. Which ones?

Decision Problems, Optimization Problems

P and NP only contains decision problems. But many decision problems can be transformed in polynomial time to and from a corresponding optimization problem.

Name Given Decision Problem Optimization Problem
SHORTEST PATH Weighted graph $G$, nodes $s$ and $t$ Is there a path $p$ from $s$ to $t$ with weight $\leq k$ (for some $k$)? Find the path from $s$ to $t$ with the smallest weight
TRAVELING SALESPERSON Complete weighted graph $G$ Is there a Hamilton Cycle of $G$ with weight $\leq k$ (for some $k$)? Find the Hamilton Cycle in $G$ with the smallest weight
MINIMUM SPANNING TREE Weighted graph $G$ Is there a spanning tree in $G$ with weight $\leq k$ (for some $k$)? Find the spanning tree of $G$ with the smallest weight
VERTEX COVER Graph $G$ Is there a subset $s$ of the nodes in $G$, of size $k$ or less (for some $k$), such that every edge in $G$ has at least one endpoint in $s$? Find the smallest subset $s$ of the nodes in $G$ such that every edge in $G$ has at least one endpoint in $s$.
SATISFIABILITY A boolean formula containing 0 or more variables Is there an assignment of boolean values to variables that makes the formula true?
CLIQUE Simple graph $G$ Is there a subset $s$ of the nodes in $G$ such that all possible edges between them are present? Find the largest subset $s$ of nodes in $G$ such that all possible edges of $s$ are present.
KNAPSACK A set $S$ of items $s_i$ with weights $w_i$ and values $v_i$, and capcity $C$ Is there a set of nonnegative integers $\{n_1...n_{|S|}\}$ such that ...? Find the numbers of each item to choose that maximizes the total value without exceeding C
SUBSET SUM Set $S$ of numbers and value $k$ Is there a non-empty subset $s \subseteq S$ such that $\sum_i{s_i} = k$?
INTEGER FACTORIZATION An integer $N \neq 0$ Is there a bag of integers $b$ not including 1 or $N$ such that $\prod_i{b_i} = N$?
GRAPH COLORING Graph $G$ Is there an assignment of $\leq k$ colors to nodes in $G$ such that no two adjacent nodes have the same color? Find the smallest number of colors such that no two adjacent vertices are the same color
MAX FLOW / MIN CUT Directed weighted graph $G$, nodes $s$ and $t$ Is there a ...? Find the ...
MIN FLOW / MAX CUT Directed weighted graph $G$, nodes $s$ and $t$ Is there a ...? Find the ...
HAMILTON CYCLE Graph $G$ Is there a cycle containing every node in $G$?
EULERIAN TOUR Graph $G$ Is there a tour containing every edge in $G$?
MATCHING Graph $G$ Is there a subset $s$ of the nodes in $G$, of size $k$ or larger (for some $k$), such that no two edges in $s$ share a vertex? Find the largest set of edges in $G$ with no common vertices.
DOMINATING SET Graph $G$ Is there a subset $s$ of the nodes in $G$, of size $k$ or less (for some $k$), to which every other node in $G$ is adjacent? Find the smallest subset of nodes in $G$ to which all other nodes are adjacent.
GRAPH PARTITIONING Undirected, weighted graph $G$ Are there $n$ graphs...? Find the smallest such $n$

The Big Deal

Here are some facts:

Some quotes

The P vs. NP problem has been called "one of the most important problems in contemporary mathematics and theoretical computer science" .... That is an understatement. Not only is P vs. NP the defining question of our field; it's one of the deepest questions ever asked for which we'd know how to recognize an answer. ....If you doubt this, read the Clay Math Institute's list of million-dollar prize problems ... notice how P vs. NP stands out, not merely as the only problem of the seven relevant practically ... Does the ability to recognize an answer ...entail the ability to find an answer? We are after not projective algebraic varieties or zeros of the Riemann zeta function, but the nature of mathematical thought itself.

Scott Aaronson
If P=NP is proved by exhibiting a truly feasible algorithm for an NP-complete problem ..., the practical consequences would be stunning. First, ... many of the optimization problems important to industry could be solved. Second, mathematics would be transformed, because computers could find a formal proof of any theorem which has a proof of reasonable length.

— Stephen Cook
In 1976 when I was a graduate student in Germany, I bumped into a new professor who had been a particularly bright student .... He had been given a full professorship ... pretty much right after receiving his Doctorate. He told me straight out that he was going to solve the P=NP problem. He exuded confidence in his abilities and fairly gloated over the fact that he had a leg up on his American counterparts, because, as a German professor, he could pretty much dictate his own schedule. That is, he could go into his room, lock his door, and focus on The Problem.

Many years later I asked about this person, and I got answers indicating that no one really knew anything about him. He was still a professor as far as anyone could tell, but he had turned into a recluse and a virtual hermit, which seemed to baffle everyone.

— Rocky Ross
If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It's possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn't we already have evolved to take advantage of it?

Scott Aaronson.

Think you can win the prize? You probably won't want to approach the challenge with natural proofs.

NP-Complete Problems

A decision problem is NP-Complete (alternatively, in the set NPC), if (1) it is in NP, and (2) a polynomial-time solution for it would imply a polynomial-time solution for every problem in NP.




Coping with NP-Completeness

If you have an NP-Complete or NP-Hard problem you can

Polynomial-Time Friends

Sometimes there are special cases of NP-Complete problems that can be solved in polynomial time. And sometimes an NP-complete problem is a close cousin to one in P.

NP-Complete Special Cases or Variants in P
SAT • All clauses have at most two literals (2SAT)
• All clauses are Horn clauses (HORN SAT)
HAMILTON CYCLE • The problem is defined for edges (EULER TOUR), not vertices
• The number of...
• k = 2
• You know that the graph is planar
LONGEST PATH • You want the SHORTEST PATH instead
(LARGEST) INDEPENDENT SET • The graph is a tree