# Unit 13: P vs NP

This unit will be a very short overview of one of the most important unsolved problems in theoretical computing: Are there any problems that cannot be solved faster than a brute-force search through every possible answer? In other words (as we will soon learn), does P equal NP?

If you found an answer to this question, you would win a million dollar prize, and either solidify or destroy the security assumptions for the cryptographic algorithms we just learned. Ready?

#### Beginning of Class 40

# 1 Problems and Algorithms

This short unit is really about *hardness*:
the inherent difficulty of certain computational problems.
We already know how to analyze the big-O running time of
an algorithm and say whether it's fast or slow. But the
task now is to talk about situations where *every*
possible algorithm would be slow.

To be more precise, we'll say a **problem** is
some well-defined transformation from acceptable inputs to
correct outputs. For example, SORTING is a problem: the input
is a list of things that can be compared to each other, and the
output is the same things, in least-to-greatest order.
We didn't say exactly what steps are taken to do the ordering, just
what the output is supposed to be. In other words, a problem specifies
the "what", but not the "how".

A **algorithm** is a specific series of steps that
always correctly solves some particular problem. For example,
MergeSort is an algorithm that correctly solves the SORTING problem.

In general, there might be many algorithms that correctly solve a given problem, and some might be faster than others. Back to our example of SORTING, we know the MergeSort algorithm has running time \(O(n\log n)\) and the SelectionSort algorithm has running time \(O(n^2)\). There are probably other correct SORTING algorithms that have other running times, so how can we talk about the running time of the SORTING problem itself?

For this, we define the **inherent difficulty** of a problem
to be the fastest possible running time of *any* correct algorithm
for that problem. For SORTING, we know the inherent difficulty
is exactly \(O(n\log n)\) because we have an algorithm that exactly
matches that running time, as well as a proof from class that any
comparison-based sorting algorithm must take at least \(O(n\log n)\)
time.

# 2 Reductions

For most problems, the situation is not so simple, and we can't say for sure what exactly is the inherent difficulty of the problem. This means that we don't know for sure whether we have the fastest algorithm yet.

Fortunately, we can still make comparisons between the
inherent difficulty or problems, even if we don't know exactly
what that inherent difficulty is, using the concept of a
*reduction*.

A reduction is a way of solving one problem, using any
algorithm for another problem. For example, we saw in the previous
unit that any public-key cryptosystem can be used to solve
the key exchange problem. So we would say that
key exchange *reduces to* public-key cryptography.
This means that the inherent difficulty of public-key cryptography
is at least as much as that of key exchange.

Another example of a reduction would be between SORTING
and MIN, where the MIN problem is defined as finding the smallest
number out of a given list of \(n\) numbers. If you have any SORTING
algorithm, you can easily solve the MIN problem by first putting
the numbers in increasing order, and then just returning the first one.
Naturally this is a pretty stupid way to solve MIN, but nonetheless
it *proves* that the SORTING problem is at least as difficult
as the MIN problem. Or to put it another way, the fastest algorithm
for SORTING can't be faster than the fastest algorithm for MIN.

# 3 Some problems

Here are some problems that will be used to frame the rest of the discussion. Some of these should be familiar, some a little less so. These aren't necessarily the most important computational problems in the world, just some useful examples for the discussion.

- MIN: Finding the smallest out of a list of numbers.
- SORTING: Putting a list of numbers in least-to-greatest order.
- SHORTPATH: Find the shortest path between two points in a given graph.
- LONGPATH: Find the longest (non-repeating) path between two points in a given graph.
- DISCRETE-LOG: Given integers \(n\), \(x\), and \(y\), find a positive integer \(a\) such that \(x^a \bmod n = y\).
- FACTORIZATION: Given integer \(n\), find two positive integers \(p, q\), both greater than or equal to 2, such that \(n=pq\).
- SUBSET-SUM: Given a list of positive and negative numbers, find a subset of the list that adds up to exactly 0.
- COLORING: Given a Map that's split up into different regions or states, using the smallest number of different colors, assign a color to each region so that any regions that touch have different colors.
- PROG-EQUAL: Given the source code for two computer programs, determine whether they have exactly the same behaviour (the same output on any possible input).

If you had to order these problems from easiest to hardest, what would you do?

# 4 P

Classifying problems by difficulty is exactly what the study of
theoretical computer science is all about. The idea is to put problems
into different groups, called *complexity classes*, and then make
comparisons between the groups.

P is the first complexity class we will look at, and it has a pretty simple definition: P is the set of all problems that can be solved in polynomial-time.

Wait, what's polynomial-time? A polynomial-time algorithm has running time \(O(n^k)\), where \(n\) as usual is the size of the input, and \(k\) is any constant integer. So for example \(O(n)\), \(O(n^2)\), even \(O(\sqrt{n})\) and \(O(n^{200})\) are all considered polynomial-time, but \(O(2^n)\) is not.

Of the example problems above, we know that MIN, SORTING, and SHORTPATH are all members of the complexity class P, because we know polynomial-time algorithms for all three of them. (Remember that Dijkstra's algorithm solves SHORTPATH.)

The real question is, which of the problems above are *not* in P, and
what would that mean? Take FACTORIZATION for example. As we discussed in the
last unit, there is no known polynomial-time algorithm to factor large integers.
But that doesn't necessarily mean FACTORIZATION isn't in P, because *maybe*
there is some fast algorithm for FACTORIZATION that we just haven't found yet.
So we know for sure that SORTING is in P, but we don't know whether FACTORIZATION
is in P or not.

# 5 NP

The second complexity class we'll talk about is NP, which has a somewhat
more subtle definition than P. The most important thing to remember first is
a common point of confusion: **NP does not mean "Not P".**
Actually NP stands for "Nondeterministic polynomial-time", but that title won't
mean much to you unless you've taken a computer science theory class.
But don't worry, we can still say what NP is in a way that makes sense.

A problem is in NP if you can *check the validity of a given answer*
to the problem in polynomial-time. Notice that this doesn't say you can actually
get the answer in polynomial-time necessarily, but just that any given answer
can be quickly checked.

Let's take the COLORING problem for example: Given a map, use the smallest number of colors to assign different colors to regions that share a common border. I have no idea how to quickly come up with a coloring scheme for a given map. But if you're given a map with regional boundaries and colors on each region, you can just look through each region and check that all the bordering regions have different colors. So you can easily check the validity of an answer; that means COLORING is in NP.

FACTORIZATION is another example of an NP problem. Given an integer \(n\), and a proposed pair of factors \(p\) and \(q\), we can easily multiply \(pq\) and check it's the same number as \(n\). We don't have any idea how to find \(p\) and \(q\) quickly, but if someone claims they've found them, we can check the result.

Notice that every problem that is in P is definitely in NP also. Why? Well, if you can compute the answer in polynomial-time, checking someone else's answer can be done by performing the computation yourself, and checking it's the same as the proposed answer. Like for MIN, say you are given a list of numbers \(L\) and a proposed smallest number \(m\). In a simple \(O(n)\)-time loop, you can find the smallest number yourself, and check it's the same as \(m\). So MIN (and every other P-problem) is also a member of the set NP.

At this point it might seem like *every* problem is a member of NP, and
indeed many problems are. But not all of them! Take PROG-EQUAL, the task of determining
whether two computer programs always do the same thing. Even if someone tells you the answer
that yes, they are the same, there's no way to quickly check this answer is correct. You
couldn't even try all possible inputs and compare the outputs, because there are an infinite
number of possible computer program inputs; your task would never be done! So
PROG-EQUAL is an example of a problem which is not in P, and not in NP either.
(And we won't talk about it anymore!)

# 6 Brute-force search

NP problems share an important property: they can always be solved by doing a brute-force, exponential-time search. This is a consequence of the definition of NP itself, that you can quickly check a potential answer to see if it's valid. That means that if you want to find the correct answer, you just go through every possible answer, check if each one is valid, and return the optimal answer.

For example, one way of solving SHORTPATH would be to generate every possible path in the graph, then check if each one is an actual, valid path from point a to point b, and return whichever valid path is shortest. In the case of SHORTPATH this is a stupid algorithm, since we know a much better way of doing the same thing (Dijkstra's). But for LONGPATH, this is actually a pretty good strategy for solving the problem; we don't know any other significantly faster way to do it!

Another example is DISCRETE-LOG. Given \(n, x, y\), we could try every possible exponent \(a=1, 2, 3, 4, \ldots\) and compute every \(x^a\bmod n\), until we find one where \(x^a\bmod n = y\), and then we've found the answer.

Another way to say this is that NP is the class of all problems that can
be solved by guess-and-check. It doesn't mean that it's going to be fast to
solve them by guess-and-check — indeed, that will take exponential-time
— but it is a *possible* way to solve these problems.

# 7 The million-dollar question

To summarize so far: we know some problems are definitely in P, like SORTING and MIN.
And all these problems are definitely in NP also.
We also know some problems are definitely in NP, like FACTORIZATION and LONGPATH.
These problems *might* be in P but we don't know yet, because no one has come
up with any polynomial-time algorithms to factor integers or find the longest path in
a graph.

In fact, even though the concept of NP was introduced in 1971, since that time
there hasn't been a single problem which is *proven* to be in NP but not
in P. And of course, we also don't know for sure that every NP problem can be
solved in polynomial-time somehow. So while it seems obvious that the sets P and
NP are not exactly the same set, we don't have a proof either way whether or not
P equals NP.

If you could prove just one NP problem is not solvable in polynomial-time, that would prove that the sets P and NP are not equal. This would be the most famous result in the history of computing, and would earn you a million dollar prize from the Clay Mathematics Institute.

On the other hand, if you could prove that every NP problem can in fact be solved in polynomial time, that would prove that P=NP. This would solve the same open problem in mathematics, but would have much more dire consequences (potentially), since it would prove that the number-theoretic problems like FACTORIZATION and DISCRETE-LOG that we've based all modern cryptography on, are not so hard to solve as we have assumed. In other words, you would break the Internet.

# 8 NP-Complete Problems

The biggest progress towards solving the P vs NP question has been in classifying
some problems as NP-Complete. Formally speaking, a problem A is NP-Complete if A is a
member of NP, and *every* other NP problem can be reduced to A. In other words,
solving a single NP-complete problem in polynomial time would give you
a polynomial-time solution to every other NP problem.

It's kind of surprising that any NP-Complete problem actually exists. But many of them do! Out of the list above, LONGPATH, COLORING, and SUBSET-SUM have all been proven to be NP-Complete. That means, for example, any polynomial-time algorithm to find the longest path in a graph, can (somehow) be used to factor integers quickly. You can find a longer list of NP-complete problems on Wikipedia.

One of the interesting things here is that the two most important hard problems
for cryptography that we've seen, FACTORIZATION and DISCRETE-LOG, are *not*
known to be NP-complete. Most of the computing world seems to believe that these
are harder than the problems in P, but not quite as hard as the NP-complete ones.
Remember, if someone had a fast algorithm to solve these problems, they would be
able to quickly crack Diffie-Hellman or RSA encryption. It would be really nice
to have a proof that cracking these cryptographic protocols is hard or
"practically impossible", but no one has been able to prove that yet.
Maybe you will?