ORF523: P vs. NP, NP-completeness

We are now going to restrict our attention to Boolean functions $latex {f : \{0,1\}^* \rightarrow \{0,1\}}&fg=000000$. Computing a Boolean function is called a decision problem, since we need to decide for $latex {x \in \{0,1\}^*}&fg=000000$ whether or not it is in the set $latex {L = \{x \in \{0,1\}^* : f(x)=1\}}&fg=000000$. We call such a set $latex {L}&fg=000000$ a language.

Note that while for optimization it is more natural to consider functions with values in $latex {\{0,1\}^*}&fg=000000$ (since one needs to write down the solution of the optimization problem), if one is interested in proving hardness results it is fine to restrict to Boolean functions since one can always consider decision problems of the form ‘does the optimal solution achieve an objective value larger than $latex {t}&fg=000000$’, for some $latex {t>0}&fg=000000$ fixed beforehand. If the latter decision problem is hard, then clearly the corresponding optimization problem is hard.

We define now the class $latex {\mathbf{P}}&fg=000000$ as the set of languages $latex {L}&fg=000000$ such that there exists a Turing Machine that computes $latex {L}&fg=000000$ in polynomial time. One often says that the class $latex {\mathbf{P}}&fg=000000$ consists of ‘easy’ decision problems.

Next we define the class $latex {\mathbf{NP}}&fg=000000$ as the set of languages $latex {L}&fg=000000$ such that there exists some $latex {c > 0}&fg=000000$, and a polynomial-time Turing Machine $latex {M}&fg=000000$ with the following property:

$latex \displaystyle x \in L \Leftrightarrow \exists u \in \{0,1\}^{|x|^{c}} : M(x, u) = 1 .&fg=000000$

In words if $latex {L \in \mathbf{NP}}&fg=000000$, then for any $latex {x \in L}&fg=000000$, there exists a ‘small’ certificate $latex {u}&fg=000000$ such that if provided to the Turing Machine then it can decide in polynomial time the language $latex {L}&fg=000000$. Thus the class $latex {\mathbf{NP}}&fg=000000$ consists of decision problems for which one can easily convince someone else that a candidate $latex {x}&fg=000000$ is indeed a solution to the decision problem (that is whether or not $latex {x}&fg=000000$ is in $latex {L}&fg=000000$).

The million dollars question asks whether $latex {\mathbf{P} = \mathbf{NP}}&fg=000000$. It is widely believe that this is not the case, but nobody has been able to prove it. Informally for problems in $latex {\mathbf{NP}}&fg=000000$ one simply needs to be able to verify a solution (the certificate), while in $latex {\mathbf{P}}&fg=000000$ one needs to find the solution. In some sense the question $latex {\mathbf{P} = \mathbf{NP}}&fg=000000$ is really about the problem of creativity, and whether or not creativity ‘truly’ exists.



We define now a concept of hardness related to the class $latex {\mathbf{NP}}&fg=000000$. A language $latex {L}&fg=000000$ is $latex {\mathbf{NP}}&fg=000000$-hard if for every language $latex {L’ \in \mathbf{NP}}&fg=000000$ there exists a polynomial-time computable function $latex {f : \{0,1\}^* \rightarrow \{0,1\}^*}&fg=000000$ such that for any $latex {x \in \{0,1\}^*}&fg=000000$, $latex {x \in L’}&fg=000000$ if and only if $latex {f(x) \in L}&fg=000000$. We call the function $latex {f}&fg=000000$ a polynomial-time reduction of $latex {L’}&fg=000000$ to $latex {L}&fg=000000$. Intuitively a decision problem is $latex {\mathbf{NP}}&fg=000000$-hard if it at least as hard as any other decision problem in $latex {\mathbf{NP}}&fg=000000$.

The notion of $latex {\mathbf{NP}}&fg=000000$-hardness can be viewed as a lower bound conditioned on the fact that $latex {\mathbf{P} \neq \mathbf{NP}}&fg=000000$. Indeed, if $latex {\mathbf{P} \neq \mathbf{NP}}&fg=000000$, then $latex {\mathbf{NP}}&fg=000000$-hard decision problems cannot be decided in polynomial time.

If a language $latex {L}&fg=000000$ is $latex {\mathbf{NP}}&fg=000000$-hard, and if $latex {L \in \mathbf{NP}}&fg=000000$, then one says that $latex {L}&fg=000000$ is $latex {\mathbf{NP}}&fg=000000$-complete. It is not obvious at first sight that any such language exist. Indeed for a language to be $latex {\mathbf{NP}}&fg=000000$-complete it means that it is in $latex {\mathbf{NP}}&fg=000000$, and that it is as hard as any other language in $latex {\mathbf{NP}}&fg=000000$. In the next section we will see our first example of an $latex {\mathbf{NP}}&fg=000000$-complete language.


Boolean formulas and the satisfiability problem

Let $latex {z_1, \hdots, z_n}&fg=000000$ be Boolean variables. A Boolean formula over these variables consists of the variables and the logical operations AND ($latex {\wedge}&fg=000000$), OR ($latex {\vee}&fg=000000$), and NOT ($latex {\neg}&fg=000000$). A Boolean formula $latex {\phi}&fg=000000$ is satisfiable if there exists an assignment $latex {x \in \{0,1\}^n}&fg=000000$ to the Boolean variables (that is $latex {z_i}&fg=000000$ is assigned TRUE if $latex {x_i=1}&fg=000000$, and FALSE if $latex {x_i=0}&fg=000000$) such that the corresponding value of the formula $latex {\phi(x)}&fg=000000$ is TRUE. We define the language $latex {\mathrm{SAT}}&fg=000000$ as the set of all satisfiable Boolean formulae.

Theorem (Cook-Levin 1971) $latex {\mathrm{SAT}}&fg=000000$ is $latex {\mathbf{NP}}&fg=000000$-complete.

Proof: First it is clear that $latex {\mathrm{SAT} \in \mathbf{NP}}&fg=000000$, since it suffices to provide a truth assignment as a certificate. Now consider a language $latex {L \in \mathbf{NP}}&fg=000000$. We need to exhibit a polynomial-time algorithm that takes as input $latex {x \in \{0,1\}^*}&fg=000000$ and outputs a Boolean formula $latex {\phi_x}&fg=000000$ with the following property: $latex {x \in L}&fg=000000$ if and only if $latex {\phi_x}&fg=000000$ is satisfiable (that is we want to reduce $latex {L}&fg=000000$ to $latex {\mathrm{SAT}}&fg=000000$). Let $latex {M}&fg=000000$ be the Turing Machine that proves that $latex {L \in \mathbf{NP}}&fg=000000$ (with certificate of size $latex {c(n)}&fg=000000$ and running time $latex {t(n)}&fg=000000$, both being polynomial). The idea of the proof is that $latex {\phi_x}&fg=000000$ is a Boolean formula that encodes the run of the Turing Machine on the input $latex {x}&fg=000000$ and ‘some’ certificate (the certificate being encode as part of the Boolean variables). Let us describe now how to construct the above Boolean formula. We will use the notation:

$latex \displaystyle x \rightarrow y := \neg x \vee y .&fg=000000$

First we describe the Boolean variables involved: $latex {T_{i,\sigma,k}}&fg=000000$ (which intuitively encodes the fact that the symbol $latex {\sigma}&fg=000000$ is on the tape at location $latex {i}&fg=000000$ during the $latex {k^{th}}&fg=000000$ step of computation), $latex {Q_{q,k}}&fg=000000$ (which encodes the fact that the state of the Machine is $latex {q}&fg=000000$ during the $latex {k^{th}}&fg=000000$ step of computation), and $latex {H_{i,k}}&fg=000000$ (which encodes the fact that the head is at location $latex {i}&fg=000000$ during the $latex {k^{th}}&fg=000000$ step of computation). Note that we can restrict to $latex {i, k \leq t(n)}&fg=000000$ so that we have a polynomial number of variables.

The first ‘part’ of the formula $latex {\phi_x}&fg=000000$ describes the start configuration of $latex {M}&fg=000000$ on an input where the first portion is given by $latex {x=(x_1, \hdots, x_n)}&fg=000000$, that is

$latex \displaystyle Q_{\mathrm{START}, 1} \wedge H_{1, 1} \wedge T_{1, x_1, 1} \wedge T_{2, x_2, 1} \wedge \hdots \wedge T_{n, x_n, 1} .&fg=000000$

Note in particular that the initial symbols on the tape at location $latex {i=n+1, \hdots, n+c(n)}&fg=000000$ are left free, which is the critical idea since then they can model any possible certificate. The next parts of the formula will model the computation steps, which are of the form (assuming the head moves right for sake of notation)

$latex \displaystyle \left( H_{i,k} \wedge Q_{q,k} \wedge T_{i, \sigma, k} \right) \rightarrow \left( H_{i+1,k+1} \wedge Q_{\delta(q,\sigma)_1,k} \wedge T_{i, \delta(q,\sigma)_2, k+1} \right) ,&fg=000000$

with the additional constraints that there is only state (respectively one head position and one symbol per location) at each time

$latex \displaystyle \left( Q_{q,k} \rightarrow \wedge_{q’ \neq q} \ \neg {Q}_{q’,k} \right) \wedge \left( H_{i,k} \rightarrow \wedge_{i’ \neq i} \ \neg {H}_{i’,k} \right) \wedge \left( T_{i,\sigma, k} \rightarrow \wedge_{\sigma’ \neq \sigma} \ \neg {T}_{i,\sigma’,k} \right),&fg=000000$

as well as the fact that a symbol can change only if the head is at the corresponding location ($latex {\sigma \neq \sigma’}&fg=000000$ in the following formula)

$latex \displaystyle \left( T_{i, \sigma, k} \wedge T_{i, \sigma’, k+1} \right) \rightarrow H_{i,k} .&fg=000000$

Taking the AND of the above formulae over all $latex {q, i, k, \sigma}&fg=000000$ and $latex {\sigma’ \neq \sigma}&fg=000000$, and the AND with the formula that encodes the fact that when the Machine halts its output is $latex {1}&fg=000000$, one obtains the formula $latex {\phi_x}&fg=000000$ which is indeed polynomial-time computable. Clearly if $latex {x \in L}&fg=000000$ then there exists a satisfying assignment that satisfies $latex {\phi_x}&fg=000000$ (assigning the variables $latex {T_{i, \sigma, 1}, i=n+1, \hdots, n+c(n)}&fg=000000$ to the value of a valid certificate, and the rest of the variables to what would happen during the computation of the Turing Machine $latex {M}&fg=000000$ with this certificate), and the converse is also clearly true. $latex \Box&fg=000000$


More NP-complete problems

By now thousands of problems are known to be $latex {\mathbf{NP}}&fg=000000$-complete. Here I just want to give a list of a few interesting examples. Many of these examples are languages over pairs $latex {(G,k)}&fg=000000$ where $latex {G = (V,E)}&fg=000000$ is a graph and $latex {k}&fg=000000$ is an integer. The language is then usually the set of such pairs such that in $latex {G}&fg=000000$ there exists a subgraph with at least $latex {k}&fg=000000$ vertices and with a certain prespecified structure.


$latex {\mathrm{3SAT}}&fg=000000$

A litteral is a Boolean variable $latex {z_i}&fg=000000$ or its negation $latex {\neg {z_i}}&fg=000000$, a clause is an OR of litterals (such as $latex {z_1 \vee \neg {z}_2 \vee z_5}&fg=000000$), and a CNF is a Boolean formula which is an AND of clauses. A $latex {k}&fg=000000$CNF is a CNF formula in which all clauses contain at most $latex {k}&fg=000000$ literals. We denote by $latex {\mathrm{kSAT}}&fg=000000$ the language of all satisfiable $latex {k}&fg=000000$CNF formulae. One can show that $latex {\mathrm{3SAT}}&fg=000000$ is $latex {\mathbf{NP}}&fg=000000$-complete (by reducing $latex {\mathrm{SAT}}&fg=000000$ to $latex {\mathrm{3SAT}}&fg=000000$). One can also show that $latex {\mathrm{2SAT} \in \mathbf{P}}&fg=000000$. The latter statement is easy to understand: a clause with $latex {2}&fg=000000$ variables is a statement of the form $latex {a \rightarrow b}&fg=000000$, thus a $latex {2}&fg=000000$CNF can be represented as a graph of implications (over the Boolean variables and their negation). Verifying the statisfiability of the formula is then equivalent to searching for paths from a variable to its negation.


$latex {\mathrm{INDSET}}&fg=000000$

Does a given graph contain a subgraph of size at least $latex {k}&fg=000000$ with no edges between them (such a subgraph is called an independent set)? This ‘question’ (i.e., the corresponding language over pairs of graph and integers) is $latex {\mathbf{NP}}&fg=000000$-complete.

Let us see how to prove this claim. First it is clear that $latex {\mathrm{INDSET} \in \mathbf{NP}}&fg=000000$. Thus it suffices now to show how to reduce (in polynomial time) any instance of $latex {\mathrm{3SAT}}&fg=000000$ to an instance of $latex {\mathrm{INDSET}}&fg=000000$. Specifically, we show how to map a $latex {m}&fg=000000$-clause 3CNF $latex {\phi}&fg=000000$ to a graph $latex {G}&fg=000000$ with $latex {7m}&fg=000000$ vertices and such that $latex {\phi}&fg=000000$ is satisfiable if and only if $latex {G}&fg=000000$ contains an independent set of size at least $latex {m}&fg=000000$. The idea is very simple: first for any clause $latex {C}&fg=000000$ in $latex {\phi}&fg=000000$ one associates a cluster of $latex {7}&fg=000000$ vertices in $latex {G}&fg=000000$ such that each vertex in this cluster corresponds to one of the possible satisfying assignment to the three variables involved in $latex {C}&fg=000000$ (we repeat one of the assignment in case the clause $latex {C}&fg=000000$ involves only one or two variables). Then one put an edge between any two vertices in the same cluster, and also an edge between any two vertices that correspond to two inconsistent assignment to the Boolean variables. A minute of thinking shows that clearly this graph has the property we were looking for, and clearly one can construct it in polynomial time.


$latex {\mathrm{CLIQUE}, \mathrm{VERTEXCOVER}, \mathrm{CUT}}&fg=000000$

The following ‘questions’ can be shown to be $latex {\mathbf{NP}}&fg=000000$-complete via a reduction to $latex {\mathrm{INDSET}}&fg=000000$:

  • Does a graph contain a clique (a subgraph where any two distinct vertices is connected) of size at least $latex {k}&fg=000000$?
  • Does a graph contain a vertex cover (a subset of vertices $latex {S}&fg=000000$ such that any edge in the graph always have one endpoint $latex {S}&fg=000000$) of size at most $latex {k}&fg=000000$?
  • Does a graph contain a cut of weight at least $latex {k}&fg=000000$ (i.e. a subset of vertices $latex {S}&fg=000000$ such that there is at least $latex {k}&fg=000000$ edges with one endpoint in $latex {S}&fg=000000$ and one endpoint in $latex {S^c}&fg=000000$)?


$latex {\mathrm{PARTITION}}&fg=000000$

The following problem is interesting because it looks extremely simple, yet it is $latex {\mathbf{NP}}&fg=000000$-complete. Given $latex {n}&fg=000000$ integers $latex {a_1, \hdots, a_n}&fg=000000$, does there exist $latex {S \subset \{1, \hdots, n\}}&fg=000000$ such that $latex {\sum_{i \in S} a_i = \sum_{i \in S^c} a_i}&fg=000000$?

This entry was posted in Theoretical Computer Science. Bookmark the permalink.