P, NP, and NP-hardness

P and NP

In the last lecture, we saw Karp (polynomial time many-one) reductions as a way to show that one problem is “harder” than another. Specifically, if A \leq_P B, then a polynomial time algorithm for problem B would yield a polynomial time algorithm for problem A. On the other hand, if there is no polynomial time algorithm for A, then there is no polynomial time algorithm for B. In this lecture, we refine these ideas to describe an entire collection of problem that likely don’t have polynomial time algorithms.

Whether or not a certain kind of algorithm exists can be used to define complexity classes of certain (decision) problems. There a couple complexity classes that are particularly well-studied. P is the set of decision problems A that can be solved in Polynomial time.

These are the problems we can solve “efficiently” for a certain definition of efficiently. Equivalently, there is a function Q_A : \{0, 1\}^* \to \{\text{False}, \text{True}\} where evaluating Q_A(x) takes \text{poly}(|x|) time Q_A returns whether x is a Yes instance for A.

There’s something peculiar about Independent Set, however. Suppose the answer for an input (G = (V, E), k) is Yes. That means there exists a subset S \subseteq V such that no two vertices in S share an edge in G. If you were to tell me what vertices belong to the subset S, I could easily verify that to be the case by simply checking that no pair of vertices in S share an edge. One might say the subset S serves as a certificate for the answer being Yes, and this idea leads to our second complexity class.

NP is the set of decision problems A for each Yes instance x of A comes with a certificate that can be verified in polynomial time. Formally, A \in \text{NP} if there exists a function R_A : \set{0, 1}^* \times \set{0, 1}^* \to \{\text{False}, \text{True}\} where evaluating R(x, y) takes \text{poly}(|x|, |y|) time and given input string x, the output for A is Yes if and only if there exists some certificate y such that

The definition probably should be difficult to parse at this point, but it will hopefully make more sense as we look over various examples.

NP does not stand for “not polynomial”. Instead, it stands for Non-deterministic Polynomial time. An equivalent definition for NP is that it contains languages that can be decided by a non-deterministic Turing machine that guesses from a constant number of possible state changes to make at each transition and uses at most a polynomial number of transitions no matter which guesses it makes. The certificate in the first formal defintion models the correct sequence of non-deterministic decisions to make to have the Turing machine reach an accept state. We didn’t go over non-deterministic Turing machines at all, so the first definition is probably the one you should reach for if you want to think about this formally.

The last example demonstrates an important relationship between the two complexity classes:

Theorem: \text{P} \subseteq \text{NP}.

Proof: For all A \in \text{P}, verifier R_A(x, y) = Q_A(x). In other words, we can ignore any given certificate and instead solve the problem from scratch.

There’s another less famous complexity class called EXP, the decision problems that can be solved in 2^{\text{poly}(n)} time.

Theorem: \text{NP} \subseteq \text{EXP}.

Proof: For all A \in \text{NP}, we can solve input x for A by trying every possible certificate y of length \text{poly}(|x|) (the polynomial is fixed for each problem so you know what it is) and running R(x, y). There are “only” 2^{\text{poly}(n)} choices for y.

The most important open in problem in theoretical computer science, maybe even all of computer science or all of science, is whether having an efficient verifier is actually different from having an efficient deterministic algorithm. In other words, is P = NP?

If it were true, and the polynomial time algorithms for problems in NP were actually efficient in practice, it would make it much easier to design new medicines, or do your homework (although GenAI has gotten pretty good at that). On the other hand, it would also ruin most traditional forms of cryptography. That seems bad.

The vast majority of computer scientists believe \text{P} \neq \text{NP}. The main reason is that there are many, many very important problems in NP for which we don’t know efficient deterministic algorithms, and there are other good reasons for the belief, so I’m not concerned about being proven wrong right now.

NP-hard, NP-complete, and SAT

We say decision problem B is NP-hard if for all problems A \in NP, we have A \leq_P B. The particular reduction to B is going to be different for each choice of A \in \text{NP}, but all they all take polynomial time (the polynomial may very for choice of A). If a problem is NP-hard, then \text{P} \neq \text{NP} would imply it does not have a polynomial time algorithm.

Now, what would be really interesting is if such a problem B was also in NP. Then the inverse would be true: P = NP would imply B does* have a polynomial time algorithm. We call such a (hypothetical) problem *NP-complete. But does such a problem even exist? Yes! But now I need to define it.

Consider a boolean formula \Phi(x_1, x_2, \dots, x_n) in n variables. Each x_i is a variable. For each variable x_i, \Phi might have one or more literals x or its inverse \bar{x}. Formula \Phi is in conjunctive normal form if it is the conjunction (and) of several clauses where each clause is the disjunction (or) of several literals.

(CNF) Satisfiability (SAT): Given a Boolean formula \Phi in conjunctive normal form, is there an assignment of True or False to each variable such that \Phi evaluates to True?

I want to emphasize that some variables appear in multiple clauses but may use opposite literals. Satisfying a subset of clauses might make it impossible to satisfy another subset!

Theorem (Cook-Levin): SAT is NP-complete.

We can see \text{SAT} \in \text{NP}, because you can use the satisfying assignment as the certificate. I’m not going to try to prove NP-hardness, though. In short, given for problem $A \in \text{NP}, given an input x, you can create a very large (but polynomial size!) Boolean formula \Phi_x that uses y as its variable input and returns R_A(x, y). There’s a certificate for x if and only if you can set the bits of y to make R_A output \text{True}. And therefore, \text{SAT} \in \text{P} if and only if P = NP.

3SAT

So there’s at least one NP-complete problem. And it turns out to be a pretty important one, because you may end up doing reductions to SAT as part of solving other problems. But the problem is also, kind of by definition, fairly general. Of course it’s hard to work with arbitrary (CNF) Boolean formulas. They can be used to describe so many things.

But it turns out there are a lot of NP-complete and other NP-hard problems B. In principle, we could prove that a problem C is NP-hard by following Cook and Levin’s lead: Describe how to take an arbitrary A \in \text{NP} and translate its instances into an instance of C. But working at that level of abstraction is too tedious and time consuming.

Instead, to prove a problem C is NP-hard, it suffices to describe a Karp reduction from any other NP-hard problem B to problem C. Indeed, for any A \in \text{NP}, we’d have A \leq_P B and B \leq_P C, implying A \leq_P C.

Right now, the only NP-hard problem we know about is SAT. And it’s so broad. Is there any hope of reducing from them? The trick is to start by showing a much more restrictive problem is NP-hard. Then we can use it as the basis for all future reductions. A 3CNF Boolean formula is a CNF formula with exactly three literals per clause.

3CNF-SAT (3SAT): Given a Boolean formula \Phi in 3CNF form, is there an assignment of True or False to each variable such that \Phi evaluates to True?

Theorem: 3SAT is NP-complete. Proof (sketch): 3SAT is in NP, because we can use the satisfying assignment as the certificate (it’s SAT again, after all.) For SAT \leq_P 3SAT, suppose we’re given a CNF Boolean formula \Phi. TODO: Describe the reduction. For now, see Erickson’s book!