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

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.

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

**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$ |

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.

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

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

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 |

- The P versus NP Page
- A Nice Explanation of the P vs. NP Problem from MIT News
- The Complexity Zoo
- Wikipedia's List of NP Complete Problems
- NP-Completeness on xkcd: TSP, Restaurant Orders.
- David Johnson's NP-Completeness Columns
- Slides from a presentation by Uriel Feige.
- Blog posts and papers by Scott Aaronson: