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

Definitions

Informally:

The class $\textsf{NP}$ is the set of all functions $f$ for which, given any $x$ and $y$, you can check, in polynomial time, whether or not $f(x,y)$ is true.
The class $\textsf{P}$ is the set of all functions $f$ for which, given any $x$, you can find, in polynomial time, a value $y$ for which $f(x,y)$ is true.

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 $\textsf{P}$ are also in $\textsf{NP}$.

Examples

The following problems are all in $\textsf{NP}$:

SHORTEST PATH: 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$?
TRAVELING SALESPERSON: Given complete weighted graph $G$ and value $k$, is there a Hamilton cycle $c$ in $G$ such that $weight(c) \leq k$?
MINIMUM SPANNING TREE: Given weighted graph $G$ and value $k$, is there a spanning tree $t$ such that $weight(t) \leq k$?
VERTEX COVER: Given graph $G$ and value $k$, is there a vertex cover $s$ for $G$ such that $|s| \leq k$?

These are in $\textsf{NP}$ because we can check in polynomial time:

Whether $p$ is a path in $G$ with weight $\leq k$
Whether $p$ is a cycle in $G$ visiting every node and has weight $\leq k$
Whether $t$ is a spanning tree of $G$ with weight $\leq k$
Whether $s$ is a vertex cover of $G$ and has $\leq k$ nodes

Exercise: Argue why these are all polynomial-time checkable.

Exercise: Two of the above problems are currently known to be in $\textsf{P}$. Which ones?

Here are some more examples:

SATISFIABILITY: Given a boolean formula with variables $x_1, x_2, \dots, x_n$, is there an assignment of boolean values to the $x_i$’s that makes the formula true?
SUBSET SUM: Given a 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: Given an integer $N \neq 0$, is there a bag of integers $b$ not including 1 or $N$ such that $\prod_i{b_i} = N$?
HAMILTON CYCLE: Given a graph $G$, is there a cycle that visits each vertex exactly once?
EULER TOUR: Given a graph $G$, is there a tour that visits each edge exactly once?

Decision and Optimization Problems

$\textsf{P}$ and $\textsf{NP}$ only contain 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$ with 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$
CLIQUE	Simple graph $G$	Is there a complete subgraph $s$ of $G$ of size $k$ or greater (for some $k$)?	Find the largest complete subgraph of $G$.
KNAPSACK	A set $S$ of items $s_i$ with weights $w_i$ and values $v_i$, and capacity $C$	Is there a set of nonnegative integers $\{n_1...n_{\|S\|}\}$ such that $\sum_i{n_i w_i} \leq C$ and $\sum_i{n_i v_i} \geq k$ (for some $k$)?	Find the numbers of each item to choose that maximizes the total value without exceeding C
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 ...
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 all other nodes in $G$ are 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:

$\textsf{NP}$ consists of thousands of useful problems that need to be solved every day.
Some, but not all, of these are in $\textsf{P}$.
For the rest, the fastest known algorithms run in worst-case exponential time.
Although no one has found polynomial-time algorithms for these problems, no one has proven that no such algorithms exist for them either!
In fact, it is quite possible that all problems in $\textsf{NP}$ are solvable (decidable) in polynomial time: no one knows whether $\textsf{P} = \textsf{NP}$ or $\textsf{P} \ne \textsf{NP}$.
Most computer scientists think they are not equal
If they are equal, and the polynomial-time algorithms for $\textsf{NP}$-complete problems are feasible rather than galactic, then the world would be a very different place: it would mean it is as easy to find solutions as it is to check them.
The INTEGER FACTORIZATION problem that makes RSA secure, would be insecure if $\textsf{P} = \textsf{NP}$ and the polynomial-time algorithms are efficient.
The Clay Mathematics Institute will award a one-million dollar prize to anyone that answers the $\textsf{P} = \textsf{NP}$ question.

Here’s some commentary:

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? Thousands of brilliant minds have tried. But the proof, assuming one even exists (!), won’t be easy. It may even require inventing entirely new mathematical techniques.

In fact, there are at least three barriers that show that the usual mathematical techniques we have now cannot solve the problem!

The relativization barrier shows that diagonalization techniques will not work.
The natural proofs barrier shows that known circuit techniques will not work.
The algebrization barrier shows that more recent techniques also will not work.

Exercise: Read about these barriers in the paper by Arthur Vale.

NP-Complete Problems

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

The first problem shown to be $\textsf{NP}$-Complete was SAT—the Boolean formula satisfiability problem—by Stephen Cook in 1971. He did this by showing that every problem in $\textsf{NP}$ can be reduced to SAT in polynomial time. In a 1972 paper, Richard Karp showed a bunch of other problems could be reduced to SAT, and others to those, showing 21 more $\textsf{NP}$-Complete problems. Since then, thousands of problems have been shown to be $\textsf{NP}$-Complete.

Coping with NP-Completeness

Since we don’t know whether $\textsf{P} = \textsf{NP}$, we just don’t have any general efficient solutions to $\textsf{NP}$-complete problems. We have some options:

Write an implementation using intelligent backtracking. This will solve the problem exactly but there will be inputs for which the run time is still longer than your lifetime.
Write something that looks for special input cases and solves them specially, e.g. for SUBSET SUM having all positive inputs and a relatively small value of $k$, there’s a pretty fast dynamic programming solution.
Write an implementation using randomization or heuristics, that runs quickly but fails to give a correct answer a certain small percentage of the time.
For optimization problems, write something that runs quickly and gives an answer that is not optimal, but not too far from optimal (an approximation algorithm).

We’d use the same strategies after $\textsf{P} \neq \textsf{NP}$ is proven, or after $\textsf{P} = \textsf{NP}$ is proven but with a galactic lower bound.

Polynomial-Time Friends

Sometimes there are special cases of NP-Complete problems that can be solved in polynomial time. And sometimes an $\textsf{NP}$-complete problem is a close cousin to one in $\textsf{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...
3-DIMENSIONAL MATCHING	• 2-DIMENSIONAL MATCHING
GRAPH k-COLORING	• k = 1 • 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
(SMALLEST) VERTEX COVER
INTEGER LINEAR PROGRAMMING	• LINEAR PROGRAMMING

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

TODO

Summary

We’ve covered: