What is P vs. NP?

To P or (N)ot to P?

Even if you have never heard of Computational Complexity theory, you might be familiar with the phrase: “P vs. NP”, but what does that even mean? Who are P and NP? Why are they fighting, and why should I care?

As to the latter question: the P vs. NP problem is one of the Clay Mathematics Institute’s $7$ millenium problems ($6$ of which, including P vs. NP, are unsolved), for which a solution yields the solver a prize of $$1$ million in U.S currency, immense academic prestige, massive breakthroughs in several fields of science, and never losing two truths and a lie ever again.

Loosely speaking the question pertains to whether a certain type of problems is fundamentally harder (for a “computer”) to solve than others. P represents the class of problems solvable in polynomial time (colloquially thought of as efficiently/quickly), while NP represents the class of problems where, if a solution is found, it can be verified to be correct in polynomial time.

To elucidate further consider the following two graph problems.

Let $G$ be some graph, meaning a set of vertices/points connected by edges/lines.

A Eulerian cycle visits every edge exactly once. This problem is efficiently solvable: essentially, one checks that the graph is connected and that every vertex is connected to an even number of other vertices.

A Hamiltonian cycle visits every vertex exactly once. If someone gives us such a cycle, we can check it quickly. But finding one is NP-complete.

So two problems that sound almost identical behave very differently:

If $\text{P} \neq \text{NP}$, then determining whether a graph has a hamiltonian cycle is fundamentally harder (for a “computer”) to determine. If $\text{P} = \text{NP}$, then every problem as hard as Hamiltonian cycle could be solved “quickly” and this would undoubtedly have incredible consequences including, but not limited to:

• you waking up with an empty bank account, as many cryptographic systems rely on computational problems being infeasible to solve in practice,
• potentially huge advances in drug discovery, enzyme design, vaccines, etc. as searching amino-acid sequences for desired structure is NP-hard,
• cheaper transport and better emergency service response since finding optimal routes is NP-hard,
• millions of computer scientists scratching their heads at this (in their opinion) marvelously unlikely outcome.

So the latter outcome would have immense implications on the real world, while the former outcome is perhaps the more philosophically interesting.

Sadly, or perhaps thankfully depending on which consequences you look at, most Computational Complexity theorists do not believe that $\text{P} = \text{NP}$, as proving that $\text{P} = \text{NP}$ would be exceedingly simple to prove compared to the alternative. In fact, preprint servers such as arXiv or (the more dubious) viXra, are littered with false proofs that $\text{P} = \text{NP}$ in the form of supposed polynomial time algorithms for NP-complete problems such as $3$-SAT. That is where deductive sciences such as Math, Theoretical Computer Science, Logic, etc. differ from empirical ones. Over the $50+$ years Computational Complexity theory has existed, no one has legitimately found such an algorithm. Thus, one might think we could decide that $\text{P} \neq \text{NP}$ on emprical evidence. However, this is not enough. We need actual mathematical proof that this is the case. What we’re left with is the brutally simple observation that

and some approaches towards closing the gap in the form of modren research programs.

Now that you’ve gotten some, possibly confusing, insight into what the P vs. NP problem is let us embark on a slightly more rigorous exposition of what Computational Complexity theory is.

The Turing Machine

You may have noticed that above I write “computer” in quotation marks. That is because theoretical computer scientists, despite the name, do not usually work directly with computers in the everyday sense. They work with models of computation: mathematically precise idealizations of what it means to compute.

This is not because laptops are beneath us, although some laptops do try very hard to deserve contempt. It is because actual computers are complicated physical objects. They have processors, memory hierarchies, operating systems, compilers, caches, cosmic-ray-induced bit flips if the universe is feeling dramatic, and fans that begin screaming the moment one opens Chrome. That is far too messy if the goal is to prove theorems.

Instead, we use simpler mathematical machines which capture the essential idea of algorithmic computation. The most famous, and still the central one for complexity theory, is the wonderful Turing machine.

Alan Turing introduced this model in his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem. The historical context is important: Turing was not trying to design a laptop. He was trying to formalize what it means for something to be computable by a finite mechanical procedure. In doing so, he helped create the mathematical foundation of computer science.

Turing was also one of the central figures in the Allied codebreaking effort at Bletchley Park during the Second World War, where his ideas contributed to the development of the Bombe machines used against Enigma-encrypted messages. But his deepest contribution to theoretical computer science is arguably not the wartime story, famous as it is. It is the fact that he gave us a precise mathematical language for talking about computation itself.

As a brief cultural aside: the movie The Imitation Game is a perfectly watchable film, but it spends much of its time on a dramatized and historically dubious version of Turing’s life, while somehow making the invention of modern computability theory look like an asside. Surely most people would agree with me that a movie about his developments in math would be much more interesting!

So what is a Turing machine?

Intuitively, a Turing machine consists of:

• a tape, divided into cells, which can store symbols,
• a head, which reads and writes one tape cell at a time,
• a finite list of internal states,
• and a transition rule telling the machine what to do next.

At each step, the machine looks at its current state and the symbol currently under the head. Based on this information, it writes a symbol, moves the head left or right, and changes state.

Formally, a deterministic Turing machine is a tuple

where:

• $Q$ is a finite set of states,
• $\Sigma$ is the input alphabet,
• $\Gamma$ is the tape alphabet, with $\Sigma \subseteq \Gamma$,
• $\delta$ is the transition function,
• $q_0 \in Q$ is the start state,
• $q_{\mathrm{acc}} \in Q$ is the accepting state,
• $q_{\mathrm{rej}} \in Q$ is the rejecting state.

The transition function has the form

This means that if the machine is in state $q$ and reads symbol $a$, then $\delta(q,a)$ tells it three things:

An input string $x \in \Sigma^\ast$ is written on the tape, the machine starts in state $q_0$, and then it follows its transition function step by step. If the machine eventually enters $q_{\mathrm{acc}}$, it accepts $x$. If it eventually enters $q_{\mathrm{rej}}$, it rejects $x$.

For decision problems, we usually think of a Turing machine as deciding a language

The language $L$ is the set of yes-instances of the problem. We say that $M$ decides $L$ if, for every input $x$,

and

In other words, a Turing machine decides a problem if it always eventually gives the correct yes/no answer.

This is the first important point: complexity theory is usually about decision problems. We ask questions like:

rather than directly asking:

This may seem restrictive, but it is a very useful convention. Search problems can often be converted into related decision problems, and decision problems give us a clean yes/no framework for reductions, hardness, and completeness.

The second important point is that Turing machines are intentionally simple. They are not meant to be realistic computers. They are meant to be mathematically clean computers. The remarkable fact is that many reasonable models of computation can simulate each other with at most polynomial overhead. So, for the purposes of classes like $\mathrm P$, $\mathrm{NP}$, and $\mathrm{PSPACE}$, the exact choice of machine model usually does not matter.

As an asside: philosophical implications like this are the things which excite me the most. Computation is seemingly such a strong and universal property that most reasonable models of it are equivalent. Things philosophical aspect of the field extends to my favourite observations such as:

• a problem is hard if and only if it is a “good computer”,
• determining whether ceirtain problems (NP) are harder than other (P) is a fundamentally hard problem (see Meta-Complexity theory for more on that!),
• and more.

This is one reason polynomial time is so central. A laptop, a Turing machine, and many other reasonable models may differ in low-level details, but they largely agree on what it means for a problem to be solvable in polynomial time. The machine model changes the implementation details, not the basic complexity class.

So when we say that a problem is solvable by a “computer”, what we usually mean is something closer to:

there exists a Turing machine which decides the corresponding language within some specified resource bound.

For example, when we define $\mathrm P$, we do not say:

the problem can be solved quickly on my laptop, assuming it has enough RAM and no Windows update begins halfway through.

We say:

That is, $L \in \mathrm P$ if there exists a deterministic Turing machine $M$ and a polynomial $p$ such that, for every input $x$, the machine decides whether $x \in L$ in at most

steps.

Here $|x|$ denotes the length of the input. The input size matters because complexity theory studies how the amount of required computation grows as the input grows.

For example, an algorithm running in time $n^2$ is polynomial time. An algorithm running in time $2^n$ is exponential time. For small inputs, this difference may not matter much. For large inputs, it becomes the difference between “done before lunch” and “the Sun has become a red giant.” This may seem silly since $2^n$ is substantially better than $n^{10000000\ldots}$ in real-world applications, but in theory the latter is better since eventually $2^n$ outgrows the latter runtime for large enough $n$. See my paper on Edge Geography for an algorithm which is theoretically better than previous techniques, but completely useless in practice!

The point of introducing Turing machines is therefore not that we secretly want to program with infinite tapes. The point is that they let us make statements like the following precise:

and

Once we have a mathematical model of computation, we can start measuring resources. Once we can measure resources, we can define complexity classes. And once we have complexity classes, the question

becomes a precise mathematical problem rather than a philosophical argument.

Time, input size, and polynomial time

Now that we have a model of computation, we can start asking complexity-theoretic questions. The most basic one is:

how many steps does the machine need before it gives an answer?

This is where input size enters the picture. If the input is a string $x$, we write $|x|$ for its length. Complexity theory is not usually interested in how long an algorithm takes on one fixed input. It is interested in how the required number of steps grows as the input gets larger.

For example, suppose an algorithm takes at most $n^2$ steps on inputs of length $n$. Then doubling the input size makes the bound roughly four times larger. This may be annoying, but it is still a very controlled kind of growth.

By contrast, an algorithm taking $2^n$ steps behaves very differently. Increasing $n$ by $1$ doubles the running time.

So we distinguish between different kinds of running time. The most important class for us is polynomial time.

An algorithm runs in polynomial time if there is some constant $k$ such that, on inputs of length $n$, it halts after at most

steps.

Equivalently, there is a polynomial $p$ such that the algorithm uses at most $p(n)$ steps on every input of length $n$.

This gives us the class $\mathrm P$.

A decision problem is in $\mathrm P$ if there is a deterministic Turing machine which decides it in polynomial time. In other words,

if there exists a deterministic Turing machine $M$ and a polynomial $p$ such that, for every input $x$, the machine decides whether $x \in L$ in at most

steps.

The class $\mathrm P$ is often informally described as the class of efficiently solvable decision problems. This is not a perfect description. An algorithm running in time $n^{1000}$ is polynomial time, but no one would call it practical with a straight face. Still, polynomial time is mathematically robust. It gives a stable notion of efficient computation that does not depend too much on the specific machine model.

An algorithm running in time $n^2$ is polynomial time. An algorithm running in time $2^n$ is exponential time. For small inputs this difference may not look dramatic, but for large inputs it becomes enormous.

Polynomial time does not automatically mean practical, and exponential time does not automatically mean impossible. But as the input size grows, polynomial and exponential running times tend to live in very different universes.

This robustness is one reason $\mathrm P$ is so central. If a problem is in $\mathrm P$, then it is not merely solvable by some clever trick on one specific computer. It is solvable efficiently in a broad, machine-independent mathematical sense.

Many familiar computational problems are in $\mathrm P$. For example:

• deciding whether a graph is connected,
• finding a shortest path in a graph with nonnegative edge weights,
• deciding whether a graph has an Eulerian cycle,
• sorting a list,
• solving a system of linear equations over a field.

These problems can look nontrivial, but they admit algorithms whose running times are bounded by polynomials in the input size.

This is the first major theme of complexity theory:

The next class, $\mathrm{NP}$, captures a different phenomenon. Some problems may not obviously be easy to solve, but once someone hands us a proposed solution, that solution is easy to check.

Certificates and the class $\mathrm{NP}$

The class $\mathrm{NP}$ is often introduced by saying that it contains the problems whose solutions can be checked efficiently.

For example, consider Hamiltonian cycle. Given a graph $G$, finding a Hamiltonian cycle may be hard. But if someone hands us a proposed Hamiltonian cycle, checking it is easy: we verify that it visits every vertex exactly once and that every consecutive pair of vertices is connected by an edge.

The proposed cycle is called a certificate or witness.

This gives the central idea behind $\mathrm{NP}$:

Formally, a language $L$ is in $\mathrm{NP}$ if there is a polynomial-time verifier $V$ and a polynomial $p$ such that, for every input $x$,

Here $y$ is the certificate. The verifier $V$ is not required to find $y$. It only has to check whether a proposed $y$ is valid.

This distinction is the heart of the P vs. NP problem.

For Hamiltonian cycle:

• the input $x$ is the graph,
• the certificate $y$ is the proposed cycle,
• the verifier checks that the proposed cycle is valid.

For satisfiability:

• the input $x$ is a Boolean formula,
• the certificate $y$ is a truth assignment,
• the verifier checks that the assignment satisfies the formula.

For Sudoku:

• the input $x$ is a partially filled board,
• the certificate $y$ is a completed board,
• the verifier checks that every row, column, and box is valid.

In all these cases, the certificate may be hard to find. But once it is found, checking it is straightforward.

This is why one often hears the slogan:

The slogan is useful, but slightly imprecise. More carefully:

• $\mathrm P$ consists of decision problems whose yes/no answer can be found in polynomial time.
• $\mathrm{NP}$ consists of decision problems whose yes-instances have polynomial-size certificates checkable in polynomial time.

Every problem in $\mathrm P$ is also in $\mathrm{NP}$. If we can decide whether $x \in L$ in polynomial time, then we do not need a meaningful certificate at all. The verifier can simply ignore the certificate and run the polynomial-time decision algorithm.

Thus,

The P vs. NP problem asks whether this containment is strict:

Equivalently:

If a yes-answer can always be verified efficiently, can it also always be found efficiently?

Most complexity theorists believe the answer is no. But no one knows how to prove it.

Showing that a problem is easy or hard

Once we have defined classes such as $\mathrm P$ and $\mathrm{NP}$, a natural question is how one actually proves that a problem belongs to one class rather than another.

To show that a problem is in $\mathrm P$, one usually gives a polynomial-time algorithm. This is the easy direction conceptually: one exhibits an efficient procedure and then analyzes its running time.

The harder direction is to argue that a problem is unlikely to admit such an algorithm. Since we do not know how to prove $\mathrm P \neq \mathrm{NP}$, we cannot usually rule out polynomial-time algorithms unconditionally for $\mathrm{NP}$ problems. What we can do, however, is give strong evidence that a problem is computationally difficult by showing that it is at least as hard as some already known difficult problem.

This is done using a reduction.

A reduction is a way of translating instances of one problem into instances of another problem so that the yes/no answer is preserved.

Informally, if problem $A$ reduces to problem $B$, then any algorithm for $B$ could also be used to solve $A$. So if $A$ is known to be hard, then $B$ must be at least as hard.

More formally, let $A$ and $B$ be decision problems. A polynomial-time many-one reduction from $A$ to $B$ is a polynomial-time computable function $f$ such that for every input $x$,

We write this as

The direction matters. The statement

does not mean that $A$ is harder than $B$ in the everyday sense. It means that $A$ can be efficiently translated into $B$. Therefore, if we could solve $B$ efficiently, then we could also solve $A$ efficiently.

So hardness flows in the opposite direction from the arrow:

A useful and pretty trivial example of a reduction is the following:

Given an undirected graph $G$ and two nodes $u,v \in G$, find the shortest path.

If we already know how to solve this problem on for undirected graphs, then we can solve the former problem by creating a directed graph $G'$ with the same vertices as $G$. Then, for each edge $\{x,y\} \in E(G)$ let $G'$ have edges $(x,y)$ and $(y,x)$. Then the shortest path from $u'$ to $v'$ is $G'$ will correspond to the shortest path between $u$ and $v$ in $G$.

NP-hardness and NP-completeness

A decision problem $B$ is called $\mathrm{NP}$-hard if every problem in $\mathrm{NP}$ reduces to $B$ in polynomial time.

A decision problem $B$ is called $\mathrm{NP}$-complete if

1. $B \in \mathrm{NP}$, and
2. $B$ is $\mathrm{NP}$-hard.

Thus, $\mathrm{NP}$-complete problems are the hardest problems in $\mathrm{NP}$, in the sense that if any one of them had a polynomial-time algorithm, then every problem in $\mathrm{NP}$ would.

In particular, if we prove that a problem is $\mathrm{NP}$-complete, then a polynomial-time algorithm for that problem would imply

Since most complexity theorists believe that $\mathrm P \neq \mathrm{NP}$, $\mathrm{NP}$-completeness is usually taken as strong evidence that no polynomial-time algorithm exists.

Our first NP-completeness proof: Clique

We will show how one proves that a problem is $\mathrm{NP}$-complete by looking at the problem $\mathrm{Clique}$.

A clique in a graph is a set of vertices all of which are pairwise adjacent. In other words, every two distinct vertices in the set have an edge between them.

The decision problem is:

For example, asking whether a graph has a clique of size $3$ means asking whether it contains a triangle.

First, let us check that $\mathrm{Clique}$ is in $\mathrm{NP}$.

A certificate for a yes-instance is simply a set of $k$ vertices. Given such a set, we can verify it quickly: check that the set has size $k$, and then check that every pair of selected vertices has an edge between them.

There are only

pairs to check, so this verification takes polynomial time in the size of the input graph. Hence,

The interesting part is hardness. To prove that $\mathrm{Clique}$ is $\mathrm{NP}$-hard, we reduce from a problem already known to be $\mathrm{NP}$-complete: $3$-$\mathrm{SAT}$.

A $3$-$\mathrm{SAT}$ instance is a Boolean formula in conjunctive normal form where each clause has exactly three literals. For example,

The question is whether there is a truth assignment to the variables that makes the whole formula true.

Suppose the formula has clauses

We build a graph as follows:

1. For every literal occurrence in every clause, create one vertex.
2. Do not put edges between vertices from the same clause.
3. Put an edge between two vertices from different clauses exactly when the two corresponding literals are compatible, meaning they are not contradictory literals like $x$ and $\neg x$.

The target clique size is $m$, the number of clauses.

Why does this work?

If the formula is satisfiable, then every clause has at least one true literal. Choose one true literal from each clause. These choices give $m$ vertices in the constructed graph. Since they all come from a single satisfying assignment, no two selected literals contradict each other. Therefore all selected vertices are connected by edges, so they form a clique of size $m$.

Conversely, suppose the constructed graph has a clique of size $m$. Since no edges were added between vertices from the same clause, the clique must contain one vertex from each clause. Since all vertices in the clique are pairwise adjacent, no two chosen literals contradict each other. Therefore we can assign truth values so that all chosen literals are true. This makes every clause true, so the original formula is satisfiable.

Thus,

The construction clearly takes polynomial time: we create one vertex per literal occurrence and check pairs of literal occurrences to decide which edges to add. Therefore we have a polynomial-time reduction

Since $3$-$\mathrm{SAT}$ is $\mathrm{NP}$-complete, this shows that $\mathrm{Clique}$ is $\mathrm{NP}$-hard. Since we already showed that $\mathrm{Clique} \in \mathrm{NP}$, we conclude that

The interactive construction below shows exactly this reduction.

Beyond $\mathrm P$ and $\mathrm{NP}$

The classes $\mathrm P$ and $\mathrm{NP}$ are central, but they are only the beginning of the complexity-theoretic zoo. Complexity theory studies many different resources: time, space, randomness, interaction, circuit size, communication, and more.

A useful first hierarchy to keep in mind is

The class $\mathrm P$ contains the decision problems solvable in polynomial time by a deterministic Turing machine.

The class $\mathrm{NP}$ contains the decision problems whose yes-instances have polynomial-size certificates verifiable in polynomial time.

The class $\mathrm{PSPACE}$ contains the decision problems solvable using only polynomial amount of memory. The computation may take a very long time, but it is only allowed to use polynomially many tape cells.

The class $\mathrm{EXPTIME}$ contains the decision problems solvable in exponential time, for example time bounded by something like

for some polynomial $p$.

Why do we have the containments above?

First,

because if we can solve a problem in polynomial time, then we can certainly verify yes-instances in polynomial time: the verifier can simply ignore the certificate and solve the problem directly.

Next,

Intuitively, an $\mathrm{NP}$ machine can be thought of as searching over polynomial-size certificates. A deterministic machine can simulate this search using polynomial space: it tries certificates one by one, reusing the same memory each time. This may take exponential time, but it does not require exponential space.

Finally,

If a machine only uses polynomially many tape cells, then it has only exponentially many possible configurations. If it runs for longer than that without halting, some configuration must repeat. So any polynomial-space computation can be simulated within exponential time.

However, the diagram is much less understood than it may look. We know some separations, but many of the most important ones remain open. In particular, we do not know whether

nor do we know whether

We do know, by the time hierarchy theorem, that

So somewhere between $\mathrm P$ and $\mathrm{EXPTIME}$, at least one of the containments above must be strict. The maddening part is that we do not know exactly where the first strict jump occurs.

There are many other important classes too.

The class $\mathrm{coNP}$ contains problems whose no-instances have efficiently checkable certificates. For example, the complement of satisfiability asks whether a Boolean formula is unsatisfiable. A yes-instance of this complement is a formula with no satisfying assignment. It is not known whether such claims always have short efficiently checkable proofs in the same sense that satisfiable formulas do.

So we also do not know whether

Randomness gives rise to classes such as $\mathrm{BPP}$, which captures problems solvable in polynomial time by randomized algorithms with a small probability of error. Interaction gives rise to classes such as $\mathrm{IP}$, where a verifier interacts with a powerful prover. Counting gives rise to classes such as $\mathrm P$, where the goal is not merely to decide whether a solution exists, but to count how many solutions there are.

The P vs. NP problem is the famous front door. But behind it is a much larger landscape of questions about time, space, proof, randomness, interaction, and the limits of efficient reasoning.