What is P vs. NP? · Thobias Høivik

To P or (N)ot to P?

Even if you have never studied theoretical computer science, you may have heard the phrase P vs. NP.

It is one of the Clay Mathematics Institute’s seven Millennium Prize Problems ( $6$ (currently maybe $5$ ) of which, including P vs. NP, remain unsolved), and solving it earns you one million dollars, immense academic prestige, and the ability to never lose two truths and a lie again.

But the actual question is much more interesting than the prize.

Imagine I give you a completed Sudoku.

Checking that I have solved it correctly is simple. You can look through the rows, columns and boxes and verify that the rules are obeyed.

Now imagine that instead I hand you the unfinished Sudoku and ask you to find a solution.

That is a rather different job.

One task asks you to find something.

The other asks you to check something that has already been found.

And, at an intuitive level, P vs. NP asks:

Whenever a correct answer can be checked efficiently, can an answer also be found efficiently?

This is what I want to try and elucidate. Everything else will be to add mathematical rigor to this idea along with some demos for inution (hopefully).

Make it precise

Strictly speaking, complexity theory usually studies decision problems: questions whose answer is yes or no.

The class $\mathrm P$ contains those decision problems which can be decided in polynomial time by a deterministic Turing machine.

The class $\mathrm{NP}$ contains those decision problems whose yes-instances have polynomial-size certificates which can be verified in polynomial time.

Thus the question is

\mathrm P \stackrel{?}{=} \mathrm{NP}.

The informal phrase “finding a solution” is useful intuition, but the formal question concerns deciding whether a solution exists.

Finding vs checking

Here is another example.

A graph is just a collection of points, called vertices, with some pairs joined by lines, called edges (see the recommended prerequisites for more details).

Suppose I ask whether a graph contains a route that visits every vertex exactly once and eventually returns to where it started.

Such a route is called a Hamiltonian cycle, usually seen in an introductory graph theory course or discrete math course.

Finding one can require searching through an enormous number of possibilities. Side note: Computers are stupid so we usually consider brute force strategies representing the worst case. In that case there are exponentially many paths to check.

But suppose somebody hands you this:

“Here is the Hamiltonian cycle.”

Now your job as the pedantic skeptic is simple.

You simply walk around the proposed route and check:

does it use real edges?

does it visit every vertex?

does it visit each vertex exactly once?

does it return to where it started?

The proposed cycle acts as evidence that the answer is yes.

In complexity theory, we usually call such evidence a certificate or witness.

This is (once you’ve done some work) the essence of NP.

A yes-answer has a reasonably small piece of evidence which can be checked efficiently.

What does NP actually mean?

A language $L$ is in $\mathrm{NP}$ if there exists a polynomial-time verifier $V$ and a polynomial $p$ such that

x\in L \quad\Longleftrightarrow\quad \exists y,\ |y|\leq p(|x|) \text{ and }V(x,y)=1.

Read this as:

$x$ is a yes-instance exactly when there exists a short certificate $y$ which the efficient checker $V$ accepts.

For Hamiltonian Cycle, $x$ encodes the graph and $y$ encodes the proposed cycle.

For SAT, $x$ encodes the Boolean formula and $y$ encodes a truth assignment.

For Sudoku, $x$ encodes the puzzle and $y$ encodes a completed board.

There is an equivalent definition using nondeterministic Turing machines: $\mathrm{NP}$ is precisely the class of problems decidable in polynomial time by such a machine.

Intuitively, a nondeterministic machine is allowed to make “guesses” during its computation. It accepts an input if there exists some sequence of guesses that leads to acceptance. For NP, you can think of this as magically guessing the right certificate and then checking it efficiently.

What does “efficient” mean?

I’ve been rather blasé about the word efficient so it is time to be a bit more rigorous about what is meant.

Consider two possible running times:

n^2

and

2^n.

The first is polynomial.

The second is exponential.

For small values of $n$ , both may be perfectly manageable.

However, their “growth” are different. While manageable at small inputs, exponential quickly runs out of controll.

Interactive aside

Runtime demo

Suppose a machine performs 1 billion elementary operations per second. Slide the input size upward and watch how different running times behave.

input sizen = 20

Input size

1255075100

TypeOperationsRuntimeScale

LinearOne pass over the input.

n20 ops

< 1 microsecond

LinearithmicTypical for efficient sorting algorithms.

n log n86 ops

< 1 microsecond

QuadraticCompare all pairs of input items.

n²400 ops

< 1 microsecond

CubicA common polynomial-time upper bound.

n³8,000 ops

8.00 microseconds

ExponentialTry every subset or every Boolean assignment.

2ⁿ10^6.0 ops

1.05 milliseconds

FactorialTry every ordering or permutation.

n!10^18.4 ops

77 years

The bars use a logarithmic scale. Otherwise the polynomial rows would become invisible as soon as the exponential and factorial rows begin behaving like themselves.

Adding one to $n$ roughly changes $n^2$ by a small amount. Doubling the size of the input roughly quadruples the runtime.

Adding one to $n$ doubles $2^n$ , but the runtime grows by an astronomical amount.

This is why complexity theory makes a major distinction between polynomial and exponential running times.

Polynomial time is not synonymous with “fast in practice” (for someone like me who is interested primarily in lower bounds it kinda does, but I digress).

An algorithm taking

n^{1000000}

steps is polynomial-time and also an excellent algorithm if your goal is to ensure the heat death of the universe occurs first.

So not every polynomial time algorithm is practical. The thing that distinguishes polynomial time from exponential is the growth, as mentioned.

Define polynomial time properly

If the input is a string $x$ , its length is written $|x|$ .

An algorithm runs in polynomial time if there exists a polynomial $p$ such that on every input $x$ , the algorithm halts after at most

p(|x|)

steps.

Equivalently, its running time is

O(n^k)

for some constant $k$ .

The class $\mathrm P$ is

\mathrm P = \{L : L\text{ is decidable by a deterministic Turing machine in polynomial time} \}.

Now we can ask P vs. NP

We should now have what we need to tackle this concept.

Loosely speaking,

P: we can determine the answer efficiently.

NP: if the answer is yes, somebody can give us evidence that lets us verify this efficiently.

Every problem in P is automatically in NP since if I can solve the problem efficiently myself, then I certainly do not need you to give me any useful evidence. I can just solve it.

So we know

\mathrm P \subseteq \mathrm{NP},

meaning all problems in $\mathrm{P}$ are also in $\mathrm{NP}$ .

The mystery is whether NP contains anything else,

\mathrm P \stackrel{?}{=} \mathrm{NP}

In ordinary English:

Is checking really easier than solving?

Or are we simply not clever enough to have discovered the efficient algorithms yet?

Nobody knows, though we have a strong suspicion.

Most complexity theorists expect

\mathrm P\neq\mathrm{NP},

though we have no rigorous mathematical proof.

More than fifty years of failing to find polynomial-time algorithms for NP-complete problems is evidence, but not sufficient.

You can stop here

If all you wanted was to know what P vs. NP means, you now know the central idea.

P contains problems we can solve efficiently.

NP contains problems for which yes-answers have short, efficiently checkable evidence.

We know

\mathrm P\subseteq\mathrm{NP},

and we do not know whether equality holds.

Everything below this point is about what those statements really mean and how complexity theorists actually reason about hard problems.

What kind of “computer” are we talking about?

So far I have been using the word “computer”.

Actual computers contain CPUs, caches, operating systems, memory hierarchies, compilers, speculative execution, cosmic-ray-induced bit flips, and fans that start screaming the moment one opens Chrome.

That is far too much nonsense if our goal is to prove mathematical theorems.

Instead, theoretical computer science uses simplified mathematical models of computation.

The most famous is the Turing machine, arriving a while before any actual physical computer.

A Turing machine has a few simple specifications:

it has somewhere to store symbols,
it can inspect one position at a time,
it has some finite internal state,
and it has rules telling it what to do next.

At every step, it looks at what it currently sees and what state it is in, writes something, moves, and changes state.

Turing machine definition

A deterministic Turing machine is a tuple

M= (Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}}),

where $Q$ is a finite set of states, $\Sigma$ is the input alphabet, $\Gamma$ is the tape alphabet, $q_0$ is the initial state, and $q_{\mathrm{acc}}$ and $q_{\mathrm{rej}}$ are the accepting and rejecting states.

Its transition function has the form

\delta: (Q\setminus\{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times\Gamma \to Q\times\Gamma\times\{L,R\}.

Thus, given the current state and currently-read tape symbol, $\delta$ specifies

\text{new state}, \qquad \text{symbol to write}, \qquad \text{direction to move}.

A decision problem can be encoded as a language

L\subseteq\Sigma^\ast.

The machine $M$ decides $L$ if it halts on every input and

x\in L \iff M\text{ accepts }x.

The precise low-level computer usually does not matter very much for the kind of questions we are asking.

Many reasonable models of computation can simulate one another with only polynomial overhead.

That is one of the reasons polynomial time is such a useful notion.

This universality of computation is among my favourite things about theoretical computer science.

How can we say that a problem is “hard”?

Suppose I have two problems, $A$ and $B$ .

Imagine that I can take any instance of $A$ , quickly transform it into an instance of $B$ , and preserve the answer.

Then somebody who gives me a fast algorithm for $B$ has accidentally also given me a fast algorithm for $A$ .

My algorithm becomes:

\text{instance of }A \longrightarrow \text{instance of }B \longrightarrow \text{solve }B.

This is called a reduction.

If a difficult problem can be translated into your problem, then your problem must be capable of expressing at least that much computational difficulty.

Yet again, this is one of my favourite parts of this sort of thing. Philosophically, we can imagine that for each class, such as NP, there only really exists one hard problem which encapsulates that class (Finite Model Theory has cool connections to this!), and all the other problems which you can reduce to are just different encodings of this problem. Beautifully, a problem is hard if and only if it is a good computer. In fact, a problem is not decidable at all if it can simulate a Turing machine!

Define a reduction precisely

A polynomial-time many-one reduction from a decision problem $A$ to a decision problem $B$ is a polynomial-time computable function $f$ satisfying

x\in A \quad\Longleftrightarrow\quad f(x)\in B.

We write

A\leq_p B.

The direction is worth remembering.

A\leq_p B

means that solving $B$ would allow us to solve $A$ .

Therefore $B$ is at least as hard as $A$ .

NP-hard and NP-complete

Now we can describe some particularly important problems.

An NP-hard problem is powerful enough that every problem in NP can be translated into it efficiently.

An NP-complete problem is NP-hard, while also itself belonging to NP.

So an NP-complete problem has both properties:

we can efficiently check its yes-solutions,
and it is at least as hard as every other problem in NP.

This has a rather nice consequence.

If one (yes only one) NP-complete problem turns out to have a polynomial-time algorithm, then every problem in NP does.

And therefore

\mathrm P=\mathrm{NP}.

Most false proofs that $\mathrm{P} = \mathrm{NP}$ come in the form of a supposed polynomial time algorithm to solve some famous $\mathrm{NP}$ -complete problem. There are tons of these on viXra!

Formal definitions

A decision problem $B$ is $\mathrm{NP}$ -hard if, for every $A\in\mathrm{NP}$ ,

A\leq_p B.

It is $\mathrm{NP}$ -complete if

B\in\mathrm{NP}

and $B$ is $\mathrm{NP}$ -hard.

Hence, if an NP-complete problem $B$ belongs to $\mathrm P$ , then every $A\in\mathrm{NP}$ reduces to a polynomial-time solvable problem, implying

\mathrm P=\mathrm{NP}.

Watch one problem turn into another

Let us actually see a reduction.

We will translate a logical puzzle into a graph puzzle.

The first problem is 3-SAT, a variant of the canonical $\mathrm{NP}$ -complete problem SAT (see Cook-Levin!).

We are given Boolean variables which may be true or false, and conditions such as

(x\vee\neg y\vee z) \wedge (\neg x\vee z\vee w) \wedge (y\vee\neg z\vee\neg w).

Each parenthesized group is a clause.

We want to know whether there is some assignment of truth values that makes every clause true.

The second problem is Clique.

A clique is simply a collection of vertices in a graph where every selected vertex is connected to every other selected vertex.

The reduction is relatively simple.

For each clause, create vertices representing the possible literals we might choose to make that clause true.

Then connect choices from different clauses whenever those choices are compatible.

For example, choosing $x$ in one clause and $\neg x$ in another would be a contradiction, so those two vertices do not get an edge.

Now ask:

Can we choose one compatible vertex from every clause?

If we can, those vertices form a clique.

And those compatible choices describe a satisfying truth assignment.

So satisfiability has been turned into a graph problem.

Below is a demo which turns some $3$ -SAT formulas into instances of Clique using this reduction. You can play around with it and see that you can indeed find a Clique in the graph whenver the formula is satisfiable!

Visual reduction

From 3-SAT to Clique

Choose a small 3-SAT instance. The construction creates one graph vertex for each literal occurrence and connects compatible literals from different clauses. Your task is to find a clique choosing one literal from every clause.

3-SAT instanceSatisfiable

Current formula(x ∨ y ∨ ¬z) ∧ (¬x ∨ z ∨ w) ∧ (¬y ∨ z ∨ ¬w)

Clique instance

Target: find a clique of size 3.

9 vertices22 edges

Semi-rigorous proof that the reduction works

Suppose the formula consists of clauses

C_1,C_2,\ldots,C_m.

Create one vertex for every literal occurrence.

Vertices from the same clause are not adjacent.

Vertices from different clauses are adjacent exactly when their literals are not contradictory.

We ask whether the resulting graph contains a clique of size $m$ .

If the formula is satisfiable, choose one true literal from each clause. Since all chosen literals are simultaneously true, no two contradict one another. Hence all corresponding vertices are pairwise adjacent, giving a clique of size $m$ .

Conversely, suppose there is a clique of size $m$ . Since vertices from the same clause are never adjacent, the clique contains one vertex from each clause. Pairwise adjacency means that no two chosen literals contradict one another. They can therefore be extended to a truth assignment making every chosen literal, and hence every clause, true.

Thus

\varphi\text{ is satisfiable} \quad\Longleftrightarrow\quad G_\varphi\text{ contains a clique of size }m.

The construction is polynomial-time, so

3\text{-}\mathrm{SAT}\leq_p\mathrm{Clique}.

Since $3$ - $\mathrm{SAT}$ is NP-complete and Clique belongs to NP, Clique is NP-complete.

P and NP are only the entrance

Complexity theory is much bigger than P vs. NP.

Time is only one computational resource.

We can ask how much memory a computation needs.

We can allow randomness.

We can study interaction, where one computational entity tries to convince another of something.

We can ask not merely whether a solution exists, but how many solutions there are.

This creates an enormous landscape of complexity classes.

A small piece of it looks like

\mathrm P \subseteq \mathrm{NP} \subseteq \underbrace{\mathrm{PSPACE}}_{\text{perhaps my favourite class!}} \subseteq \mathrm{EXPTIME}.

We do not know whether

\mathrm P=\mathrm{NP},

and we do not know whether

\mathrm{NP}=\mathrm{PSPACE}.

We do know

\mathrm P\neq\mathrm{EXPTIME}.

So somewhere along that chain, computational power definitely increases.

We just do not know exactly where all the increases happen.

Why do these containments hold?

We have

\mathrm P\subseteq\mathrm{NP}

because a polynomial-time algorithm can itself serve as a verifier.

We have

\mathrm{NP}\subseteq\mathrm{PSPACE}

because a deterministic machine can enumerate polynomial-size certificates while reusing the same polynomial amount of memory.

Finally,

\mathrm{PSPACE}\subseteq\mathrm{EXPTIME},

because a polynomial-space machine has only exponentially many configurations. A halting computation therefore need not explore more than exponentially many distinct configurations.

By the deterministic time hierarchy theorem,

\mathrm P\neq\mathrm{EXPTIME}.

Other important classes include $\mathrm{coNP}$ , $\mathrm{BPP}$ , $\mathrm{IP}$ , and $\#\mathrm P$ .

Closing remarks

P vs. NP is usually introduced as a question about algorithms.

But I think there is a more interesting way to look at it.

It asks whether there is a fundamental difference between

discovering that something exists

and

recognizing convincing evidence once somebody shows it to you.

That distinction appears in optimization, mathematics, logic, cryptography, games, scheduling, artificial intelligence, and countless other places.

It’s also rather meta. A proof of some theorem can be thought of as a short sertificate. Meta complexity studies how “difficult” it is to prove that something is difficult, at least to my understanding. There are lots of these cool branches of complexity theory such as circuit- and algebraic circuit complexity, proof complexity, parameterized complexity (one of my personal favourites!) and more.

After decades of research, we still do not know whether that distinction reflects something fundamental about computation or merely something fundamental about our current lack of understanding.

I think this is considerably cooler than the one-million-dollar prize.