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 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 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 P are also in NP.

Examples

The following problems are all in 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$ visiting every node 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 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 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:

NP consists of thousands of useful problems that need to be solved every day.
Some of these are in P.
For the rest, the fastest known algorithms run in 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 NP are solvable (decidable) in polynomial time: no one knows whether P = NP or P ≠ NP.
Most computer scientists think they are not equal: if they are equal, 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 probably insecure if P = NP.
The Clay Mathematics Institute will award a one-million dollar prize to anyone that answers the P=NP question.

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.

TODO

Reductions

TODO

Coping with NP-Completeness

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

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 exists 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. (Ideally the implementation would announce that it wasn't sure of its answer.)
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).

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...
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