P vs NP

If you’ve ever studied CS, you’re probably familiar with the infamous P versus NP problem. In this post, I’ll try to explain why we even care about this problem, what it means to be NP-hard and NP-complete, and lastly how to show whether a given problem belongs in these categories or not.

Preliminaries

A basic understanding of models of computation would be helpful!

Why P?

Why should we draw the divide between “efficient” and “inefficient” as between P and NP in the first place? After all, an algorithm that runs in time is surely worse than one that runs in , right? One may make the argument that the former is asymptotically better than the latter, but this never felt super compelling to me.

I think a less subjective argument than “efficient vs inefficient” that justifies our special treatment of the P class is the fact that polynomials are closed under addition and multiplication. This means that even if fundamental operations started to run in rather than , a polynomial algorithm in the latter circumstance would remain polynomial in the former. In a way, this makes the notion of P machine-invariant, as long as both machines can run fundamental operations in polynomial time.

This invariance means that although P and NP were originally defined relative to the operations required by a Turing machine, we may instead replace the Turing machine—which is rather unwieldy to reason about—with a more “efficient” machine that can perform basic operations like addition, multiplication, and memory access in time, while leaving the classes P and NP undisturbed.

What is NP?

Contrary to somewhat popular belief, NP does not mean non-polynomial but rather nondeterministic polynomial, which refers to any program that a nondeterministic Turing machine (as described in models of computation) may run in polynomial time. A nice way of rephrasing this it that a problem is in NP if it can be verified in polynomial time. For instance, consider the classic NP-complete subset sum problem:

Given a list of integers and a target , determine whether there exists a subset of the integers that sums to .

To solve this, we can write a simple non-deterministic program that runs in :

1. Initialize a variable sum to 0.
2. Every time we read a new number x from the input, split the program into two branches: one where sum is incremented by x, and another where its not.
3. After processing all numbers in this fashion, our computation tree has leaves. Check if sum in any of these is equal to T.

Alternatively, if we specify a specific leaf among the possibilities to evaluate—which basically corresponds to you giving me a subset of numbers and asking me whether they sum to —this can be done in time. This is what it means to be verifiable in polynomial time.

NP-hard

We call a problem NP-hard if any other problem in NP can be reduced to this one in polynomial time. Consequently, if any NP-hard problem can be solved in polynomial time, we have proven that P = NP. We proceed to offer some classic examples of NP-hard problems and also sketch proofs of their NP-hardness.

Boolean satisfiability (SAT)

This problem is perhaps one of the most famous NP-complete problems, and the Cook-Levin theorem that proved its completeness is a landmark result in CS (for a formal proof, the stanford notes are a great resource).

The SAT problem essentially asks: given an acyclic Boolean circuit composed of AND, OR, and NOT gates that inputs bits and outputs 1 single bit, does there exist a way to set the input bits such that the output bit is ?

The intuitive reason why this is NP-complete is because if you look inside a computer, it’s also basically just composed of logic gates. Therefore, any verifier program that works in polynomial time can be rewritten as a Boolean circuit in polynomial time. Then, we can run SAT on this circuit to determine whether any input is accepted by the verifier program.

Before we move on, we should probably clarify how exactly to represent SAT problems. The typical form used is conjunctive normal form (CNF) which write the output bit as a conjunction of disjunctions like so:

denotes logical and, denotes logical or, and denotes negation. The problem is then to find whether there exists some such that the above expression evaluates to 1.

The cousin of CNF is disjunctive normal form (DNF) which swaps and . However, we prefer CNF since any boolean formula may be converted into an equisatisfiable CNF formula in polynomial time. The same is not true for DNF; for instance, the DNF expansion of

would have terms.

Exercise

We say a Boolean formula has a solution if its variables can be set such that the expression evaluates to (i.e. true).

We then say that two boolean formulas and are equisatisfiable when has a solution has a solution. How can we convert any boolean formula of length into an equisatisfiable Boolean formula with length ?

Subset sum

As described earlier, the subset sum problem asks the following:

Given a list of integers and a target , determine whether there exists a subset of the integers that sums to .

The following sketch of NP-hardness is based on notes from Cornell.

To prove NP-hardness, it’s sufficient to prove that any instance of SAT can be reduced to subset sum in polynomial time. For convenience, we will assume the SAT problem is written in CNF.

Also for convenience, we assume numbers are written in a sufficiently large base such that no carries occur during addition. We will later place a concrete upper bound on and show that the total length of the list remains polynomial in the size of the SAT instance.

First, we will create two variables , for each Boolean variable . If we include in our subset, this will correspond to setting to true; similarly, corresponds to .

Therefore, we will have to enforce the condition that for all , exactly one of and is included in our subset. This can be done by setting the th digit of each of , , and to be .

For instance, if we have three variables , we transform them into

Note

Here we write exponents of in increasing order from left to right, so denotes .

Then, we add an additional bit for each clause in CNF. In particular, if variable is in clause , we set the th digit of to 1; resp. and . For instance, if our expression is

our become

Then, our condition for finding a solution is that the 4th and 5th digits of our subset sum are both at least 1. To convert this condition back into hitting an exact target sum, let denote the number of variables in clause . Then, we can just add copies of into our list and set our target to

Exercise

Verify that a solution to this subset sum problem exists iff a solution exists to the original SAT instance.

It remains to show that the length of this list of numbers is polynomial in the size of the SAT instance. In order for no overflow to occur, we can choose . Note that each number in the list has length , and therefore the total length of the list is bounded by .

NP-complete

We call a problem NP-complete if it is both NP and NP-hard.

Exercise

Are all the NP-hard problems listed above NP-complete?

Note that there are problem which are NP-hard but not NP, such as the halting problem.

Additional resources

The following video provides a really great alternative perspective on P vs NP, framing it instead as “can you efficiently invert an efficient function?” In the companion blog post, Polylog also draws a nice connection to backpropagation.