MODULE 8:   P vs NP
Non-Deterministic Polynomial Time

In this chapter, we give the formal definition of the complexity class NP\mathsf{NP} (which stands for “non-deterministic polynomial time”), along with various examples. We then present examples of NP\mathsf{NP}-complete languages, which represent the hardest languages in NP\mathsf{NP}.

1
Non-Deterministic Polynomial Time NP
Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP})

Fix some alphabet Σ\Sigma. We say that a language LL can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM VV that takes two strings as input, and

  2. a constant k>0k > 0,

such that for all xΣx \in \Sigma^*:

  • if xLx \in L, then there exists uΣu \in \Sigma^* with uxk|u| \leq |x|^k such that V(x,u)V(x,u) accepts,

  • if x∉Lx \not \in L, then for all uΣu \in \Sigma^*, V(x,u)V(x,u) rejects.

If xLx \in L, a string uu that makes V(x,u)V(x,u) accept is called a proof (or certificate) of xx being in LL. The TM VV is called a verifier for LL.

We denote by NP\mathsf{NP} the set of all languages which can be decided in non-deterministic polynomial time.

Proposition (3COL is in NP\mathsf{NP})

3COLNP\text{3COL} \in \mathsf{NP}.

Proof

To show 3COL is in NP\mathsf{NP}, we need to show that there is a polynomial-time verifier TM AA with the properties stated in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}) (we are using AA to denote the verifier and not VV because we will use VV to denote the vertex set of a graph). Recall that an instance of the 3COL problem is an undirected graph GG. The description of AA is as follows.

def    A(graph G=(V,E),  u):1.    If u does not correspond to a 3-coloring of V, reject.2.    If there is {v,w}E where v and w have the same color, reject.3.    Else, accept.\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; A(\langle \text{graph } G = (V,E) \rangle, \; u):\\ &{\scriptstyle 1.}~~~~\texttt{If $u$ does not correspond to a $3$-coloring of $V$, reject.}\\ &{\scriptstyle 2.}~~~~\texttt{If there is $\{v,w\} \in E$ where $v$ and $w$ have the same color, reject.}\\ &{\scriptstyle 3.}~~~~\texttt{Else, accept.}\\ \hline\hline\end{aligned}

We now show that AA satisfies the two conditions stated in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}). If xx is in the language, that means xx is a valid encoding of a graph G=(V,E)G=(V,E) and this graph is 33-colorable. When uu is a 33-coloring of VV, u=O(V)|u| = O(|V|). And for this xx and uu, the verifier accepts. On the other hand, if xx is not in the language, then either (i) xx is not a valid encoding of a graph or (ii) it is a valid encoding of a graph which is not 33-colorable. In case (i), the verifier rejects (which is done implicitly since the input is not of the correct type). In case (ii), any uu that does not correspond to a 33-coloring of the vertices makes the verifier reject. Furthermore, any uu that does correspond to a 33-coloring of the vertices must be such that there is an edge whose endpoints are colored with the same color. Therefore, in this case, the verifier again rejects, as desired.

Now we show that the machine is polynomial-time. To check whether uu is a 33-coloring of the vertices takes polynomial time since you just need to check that you are given V|V| colors, each being one of 33 colors. To check that it is indeed a legal 33-coloring is polynomial time as well since you just need to go through every edge once and check for each that the endpoints are different colors.

This completes the proof that 3COL is in NP\mathsf{NP}.

Note (Steps to show a languages is in NP\mathsf{NP})

Showing that a language LL is in NP\mathsf{NP} involves the following steps:

  1. Present a TM VV (that takes two inputs xx and uu).

  2. Argue that VV has polynomial running time.

  3. Argue that VV works correctly, which involves arguing the following for some constant k>0k>0:

    • for all xLx \in L, there exists uΣu \in \Sigma^* with uxk|u| \leq |x|^k such that V(x,u)V(x,u) accepts;

    • for all x∉Lx \not \in L and for all uΣu \in \Sigma^*, V(x,u)V(x,u) rejects.

Proposition (CIRCUIT-SAT is in NP\mathsf{NP})

CIRCUIT-SATNP\text{CIRCUIT-SAT}\in \mathsf{NP}.

Proof

To show CIRCUIT-SAT is in NP\mathsf{NP}, we need to show that there is a polynomial-time verifier VV with the properties stated in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}). We start by presenting VV.

def    V(circuit C,  u):1.    If u does not correspond to a 0/1 assignment to input gates, reject.2.    Compute the output of the circuit C(u).3.    If the output is 0, reject.4.    Else, accept.\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; V(\langle \text{circuit } C \rangle, \; u):\\ &{\scriptstyle 1.}~~~~\texttt{If $u$ does not correspond to a $0/1$ assignment to input gates, reject.}\\ &{\scriptstyle 2.}~~~~\texttt{Compute the output of the circuit $C(u)$.}\\ &{\scriptstyle 3.}~~~~\texttt{If the output is $0$, reject.}\\ &{\scriptstyle 4.}~~~~\texttt{Else, accept.}\\ \hline\hline\end{aligned}

We first show that the verifier VV satisfies the two conditions stated in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}). If xx is in the language, that means that xx corresponds to a valid encoding of a circuit and there is some 0/10/1-assignment to the input gates that makes the circuit output 11. When uu is such a 0/10/1-assignment, then u=O(n)|u| = O(n) (where nn is the length of xx), and the verifier accepts the input (x,u)(x,u). On the other hand, if xx is not in the language, then either (i) xx is not a valid encoding of a circuit or (ii) it is a valid encoding of a circuit which is not satisfiable. In case (i), the verifier rejects (which is done implicitly since the input is not of the correct type). In case (ii), any uu that does not correspond to a 0/10/1-assignment to the input gates makes the verifier reject. Furthermore, any uu that does correspond to a 0/10/1-assignment to the input gates must be such that, with this assignment, the circuit evaluates to 00. Therefore, in this case, the verifier again rejects, as desired.

Now we show the verifier is polynomial-time. To check whether uu is a valid 0/10/1-assignment to the input gates takes polynomial time since you just need to check that you are given tt bits, where tt is the number of input gates. The output of the circuit can be computed in polynomial time since it takes constant number of steps to compute each gate.

This completes the proof of CIRCUIT-SAT is in NP\mathsf{NP}.

Exercise (CLIQUE is in NP\mathsf{NP})

Show that CLIQUENP\text{CLIQUE}\in \mathsf{NP}.

Solution

To show CLIQUE is in NP\mathsf{NP}, we need to show that there is a polynomial-time verifier AA with the properties stated in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}). We start by presenting AA. (We are using AA to denote the verifier and not VV because we will use VV to denote the vertex set of a graph.)

def    A(graph G=(V,E),positive natural k,  u):1.    If u does not correspond to a set SV with S=k, reject.2.    For each pair of vertices u,v in S:3.        If {u,v}∉E, reject.4.    Accept.\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; A(\langle \text{graph } G = (V,E), \text{positive natural } k \rangle, \; u ):\\ &{\scriptstyle 1.}~~~~\texttt{If $u$ does not correspond to a set $S \subseteq V$ with $|S| = k$, reject.}\\ &{\scriptstyle 2.}~~~~\texttt{For each pair of vertices $u, v$ in $S$:}\\ &{\scriptstyle 3.}~~~~~~~~\texttt{If $\{u,v\} \not \in E$, reject.}\\ &{\scriptstyle 4.}~~~~\texttt{Accept.}\\ \hline\hline\end{aligned}

We first show that the verifier AA satisfies the two conditions stated in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}). If xx is in the language, that means that xx corresponds to a valid encoding of a graph G=(V,E)G = (V,E) together with a number kNk \in \mathbb N. Furthermore, it must be the case that there is some SVS \subseteq V with S=k|S|=k such that SS forms a kk-clique. When uu is the encoding of such an SS, then u=O(n)|u| = O(n) where nn is the length of xx, and the verifier AA accepts (x,u)(x,u). On the other hand, if xx is not in the language, then either (i) xx is not a valid encoding of a graph G=(V,E)G = (V,E) together with a number kNk \in \mathbb N or (ii) it is a valid encoding G,k\langle G, k \rangle, but there is no SVS \subseteq V, S=k|S| = k, that forms a kk-clique. In case (i), the verifier rejects (which is done implicitly since the input is not of the correct type). In case (ii), any uu that does not correspond to a set SVS \subseteq V with S=k|S| = k makes the verifier reject. Furthermore, any uu that does correspond to such an SS cannot form a kk-clique. In this case, the for loop will detect this and the verifier again rejects, as desired.

Now we show the verifier is polynomial-time. Checking whether uu is a valid encoding of a set SVS \subseteq V with S=k|S| = k is polynomial time. If this check passes, then the for-loop repeats at most O(V2)O(|V|^2) many times, and the body of the loop can be carried out in polynomial time. So in total, the work being done is polynomial time.

Exercise (IS is in NP\mathsf{NP})

Show that ISNP\text{IS}\in \mathsf{NP}.

Solution

The argument is very similar to the one above. Here is the verifier:

def    A(graph G=(V,E),positive natural k,  u):1.    If u does not correspond to a set SV with S=k, reject.2.    For each pair of vertices u,v in S:3.        If {u,v}E, reject.4.    Accept.\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; A(\langle \text{graph } G = (V,E), \text{positive natural } k \rangle, \; u ):\\ &{\scriptstyle 1.}~~~~\texttt{If $u$ does not correspond to a set $S \subseteq V$ with $|S| = k$, reject.}\\ &{\scriptstyle 2.}~~~~\texttt{For each pair of vertices $u, v$ in $S$:}\\ &{\scriptstyle 3.}~~~~~~~~\texttt{If $\{u,v\} \in E$, reject.}\\ &{\scriptstyle 4.}~~~~\texttt{Accept.}\\ \hline\hline\end{aligned}

We skip the arguments for correctness and running time.

Exercise (3SAT is in NP\mathsf{NP})

Show that 3SATNP\text{3SAT} \in \mathsf{NP}.

Solution

To show 3SAT is in NP\mathsf{NP}, we need to show that there is a polynomial-time verifier VV with the properties stated in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}). We start by presenting VV.

def    V(3CNF formula F,  u):1.    If u does not correspond to a 0/1 assignment to the variables in F, reject.2.    Compute the output of the formula F(u).3.    If the output is 0, reject.4.    Else, accept.\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; V(\langle \text{3CNF formula } F \rangle, \; u ):\\ &{\scriptstyle 1.}~~~~\texttt{If $u$ does not correspond to a $0/1$ assignment to the variables in $F$, reject.}\\ &{\scriptstyle 2.}~~~~\texttt{Compute the output of the formula $F(u)$.}\\ &{\scriptstyle 3.}~~~~\texttt{If the output is $0$, reject.}\\ &{\scriptstyle 4.}~~~~\texttt{Else, accept.}\\ \hline\hline\end{aligned}

We first show that the verifier VV satisfies the two conditions stated in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}). If xx is in the language, that means that xx corresponds to a valid encoding of a 3CNF formula. Furthermore, there is some 0/10/1-assignment to the variables that makes the formula output 11. When uu is this 0/10/1-assignment, then u=O(n)|u| = O(n) (where nn is the length of xx), and the verifier accepts the input (x,u)(x,u). On the other hand, if xx is not in the language, then either (i) xx is not a valid encoding of a CNF formula in which every clause has exactly 3 literals or (ii) it is a valid encoding but the formula is not satisfiable. In case (i), the verifier rejects (which is done implicitly since the input is not of the correct type). In case (ii), any uu that does not correspond to a 0/10/1-assignment to the variables makes the verifier reject. Furthermore, any uu that does correspond to a 0/10/1-assignment to the variables must be such that, with this assignment, the formula evaluates to 00. Therefore, in this case, the verifier again rejects, as desired.

Now we show the verifier is polynomial-time. To check whether uu is a valid 0/10/1-assignment to the variables takes polynomial time since you just need to check that you are given tt bits, where tt is the number of variables. The output of the formula can be computed in polynomial time since it takes constant number of steps to compute each clause (and the number of clauses is bounded by the length of the input).

Proposition (P\mathsf{P} is contained in NP\mathsf{NP})

PNP\mathsf{P}\subseteq \mathsf{NP}.

Proof

Given a language LPL \in \mathsf{P}, we want to show that LNPL \in \mathsf{NP}. Since LL is in P\mathsf{P}, we know that there is a polynomial-time decider MM that decides LL. To show that LNPL \in \mathsf{NP}, we need to describe a polynomial-time verifier VV that has the properties described in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}). The description of VV is as follows.

def    V(x,  u):1.    Return M(x).\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; V(x, \; u ):\\ &{\scriptstyle 1.}~~~~\texttt{Return $M(x)$.}\\ \hline\hline\end{aligned}

First, note that since MM is a polynomial time decider, the line running M(x)M(x) takes polynomial time, and so VV is polynomial-time. We now check that VV satisfies the two conditions stated in Definition (Non-deterministic polynomial time, complexity class NP\mathsf{NP}). If xLx \in L, then M(x)M(x) accepts, so for any uu, V(x,u)V(x,u) accepts. For example, V(x,ϵ)V(x, \epsilon) accepts, and clearly ϵ=0x|\epsilon| = 0 \leq |x|. If x∉Lx \not \in L, then M(x)M(x) rejects, so no matter what uu is, V(x,u)V(x,u) rejects, as desired. This shows that LNPL \in \mathsf{NP}.

Definition (Complexity class EXP\mathsf{EXP})

We denote by EXP\mathsf{EXP} the set of all languages that can be decided in at most exponential-time, i.e., in time O(2nC)O(2^{n^C}) for some constant C>0C > 0.

Exercise (NP\mathsf{NP} is contained in EXP\mathsf{EXP})

Show that NPEXP\mathsf{NP}\subseteq \mathsf{EXP}.

Solution

To show NPEXP\mathsf{NP}\subseteq \mathsf{EXP}, it suffices to argue that any LNPL \in \mathsf{NP} is also in EXP\mathsf{EXP}. So take an arbitrary LNPL \in \mathsf{NP}. By the definition of NP\mathsf{NP} we know that there is some polynomial-time verifier TM VV and constant k>0k > 0 such that for all xΣx \in \Sigma^*:

  • if xLx \in L, then there is some uΣu \in \Sigma^* with uxk|u| \leq |x|^k such that V(x,u)V(x, u) accepts;

  • if x∉Lx \not \in L, then for all uΣu \in \Sigma^*, V(x,u)V(x,u) rejects.

We construct a decider AA for LL as follows.

def    A(x):1.    For all uΣ with uxk:2.        Run V(x,u) and if it accepts, accept.3.    Reject\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; A(x):\\ &{\scriptstyle 1.}~~~~\texttt{For all $u \in \Sigma^*$ with $|u| \leq |x|^k$:}\\ &{\scriptstyle 2.}~~~~~~~~\texttt{Run $V(x,u)$ and if it accepts, accept.}\\ &{\scriptstyle 3.}~~~~\texttt{Reject}\\ \hline\hline\end{aligned}

Correctness: If xLx \in L, then we know that for some uΣu \in \Sigma^* with uxk|u| \leq |x|^k, V(x,u)V(x, u) accepts. Therefore AA accepts as well. If on the other hand x∉Lx \not \in L, then for all uΣu \in \Sigma^*, V(x,u)V(x,u) rejects. Therefore AA rejects as well.

Running time: The running time of AA is O(2nC)O(2^{n^C}) for an appropriately chosen constant CC. We omit the details of this part.

2
NP-complete problems
Note (NP\mathsf{NP}-hardness and NP\mathsf{NP}-completeness)

Recall Definition (C\mathcal{C}-hard, C\mathcal{C}-complete). We use this definition in this section with C\mathcal{C} being NP\mathsf{NP}. However, our notions of NP\mathsf{NP}-hardness and NP\mathsf{NP}-completeness will be restricted to Karp reductions. As mentioned in Note (C\mathcal{C}-hardness with respect to Cook and Karp reductions), hardness and completeness is often defined using Karp reductions. We may explore some of the reasons for this in a homework problem.

Important Note (Use Karp reductions for NP\mathsf{NP}-hardness)

To show that a language is NP\mathsf{NP}-hard, you should be using Karp reductions.

Theorem (Cook-Levin Theorem)

CIRCUIT-SAT\text{CIRCUIT-SAT} is NP\mathsf{NP}-complete.

Note

Cook and Levin actually proved that SAT\text{SAT} is NP\mathsf{NP}-complete, however, the theorem is often stated using CIRCUIT-SAT\text{CIRCUIT-SAT} rather than SAT\text{SAT} because the version above is easier to prove.

Important Note (Showing a language is NP\mathsf{NP}-hard)

To show that a language LL is NP\mathsf{NP}-hard, by the transitivity of polynomial-time reductions, it suffices to show that KmPLK \leq_m^PL for some language KK which is known to be NP\mathsf{NP}-hard. In particular, using Cook-Levin Theorem, it suffices to show that CIRCUIT-SATmPL\text{CIRCUIT-SAT}\leq_m^PL.

Theorem (3COL is NP\mathsf{NP}-complete)

3COL\text{3COL} is NP\mathsf{NP}-complete.

Proof

We have already done all the work to prove that 3COL\text{3COL} is NP\mathsf{NP}-complete. First of all, in Proposition (3COL is in NP\mathsf{NP}), we have shown that 3COLNP\text{3COL} \in \mathsf{NP}. To show that 3COL\text{3COL} is NP\mathsf{NP}-hard, by the transitivity of reductions, it suffices to show that CIRCUIT-SATmP3COL\text{CIRCUIT-SAT}\leq_m^P\text{3COL}, which we have done in Theorem (CIRCUIT-SAT reduces to 3COL).

Theorem (3SAT is NP\mathsf{NP}-complete)

3SAT\text{3SAT} is NP\mathsf{NP}-complete.

Proof (Proof Sketch)

We sketch the main ideas in the proof. To show that 3SAT\text{3SAT} is NP\mathsf{NP}-complete, we have to show that it is in NP\mathsf{NP} and it is NP\mathsf{NP}-hard. We leave the proof of membership in NP\mathsf{NP} as an exercise.

To show that 3SAT\text{3SAT} is NP\mathsf{NP}-hard, by the transitivity of reductions, it suffices to show that CIRCUIT-SATmP3SAT\text{CIRCUIT-SAT}\leq_m^P\text{3SAT}. Given an instance of CIRCUIT-SAT\text{CIRCUIT-SAT}, i.e. a Boolean circuit CC, we will construct an instance of 3SAT\text{3SAT}, i.e. a Boolean CNF formula φ\varphi in which every clause has exactly 3 literals. The reduction will be polynomial-time and will be such that CC is a Yes instance of CIRCUIT-SAT\text{CIRCUIT-SAT} (i.e. CC is satisfiable) if and only if φ\varphi is a Yes instance of 3SAT\text{3SAT} (i.e. φ\varphi is satisfiable).

The construction is as follows. A circuit CC has three types of gates (excluding the input-gates): NOT, OR, AND.

image

We will convert each such gate of the circuit CC into a 3SAT\text{3SAT} formula. It is easy to verify that yi=¬xi(xiyi)(¬xi¬yi),yk=xixj(yk¬xi)(yk¬xj)(¬ykxixj),yk=xixj(¬ykxi)(¬ykxj)(yk¬xi¬xj).\begin{aligned} y_i = \neg x_i & \Longleftrightarrow (x_i \vee y_i) \wedge (\neg x_i \vee \neg y_i), \\ y_k = x_i \vee x_j & \Longleftrightarrow (y_k \vee \neg x_i) \wedge (y_k \vee \neg x_j) \wedge (\neg y_k \vee x_i \vee x_j),\\ y_k = x_i \wedge x_j & \Longleftrightarrow (\neg y_k \vee x_i) \wedge (\neg y_k \vee x_j) \wedge (y_k \vee \neg x_i \vee \neg x_j).\end{aligned} So the behavior of each gate can be represented using a Boolean formula. As an example, consider the circuit below.

image

In this case, we would let φ1=(x1y1)(¬x1¬y1)φ2=(¬y2x2)(¬y2x3)(y2¬x2¬x3)φ3=(y3¬y1)(y3¬y2)(¬y3y1y2),\begin{aligned} \varphi_1 & = (x_1 \vee y_1) \wedge (\neg x_1 \vee \neg y_1) \\ \varphi_2 & = (\neg y_2 \vee x_2) \wedge (\neg y_2 \vee x_3) \wedge (y_2 \vee \neg x_2 \vee \neg x_3) \\ \varphi_3 & = (y_3 \vee \neg y_1) \wedge (y_3 \vee \neg y_2) \wedge (\neg y_3 \vee y_1 \vee y_2), \end{aligned} and the Boolean formula equivalent to the circuit would be φ=φ1φ2φ3y3.\varphi = \varphi_1 \wedge \varphi_2 \wedge \varphi_3 \wedge y_3. This is not quite a 3SAT formula since each clause does not necessarily have exactly 3 literals. However, each clause has at most 3 literals, and every clause in the formula can be converted into a clause with exactly 3 literals by duplicating a literal in the clause if necessary.

This completes the description of how we construct a 3SAT formula from a Boolean circuit. We leave it as an exercise to the reader to verify that CC is satisfiable if and only if φ\varphi is satisfiable, and that the reduction can be carried out in polynomial time.

Theorem (CLIQUE is NP\mathsf{NP}-complete)

CLIQUE\text{CLIQUE} is NP\mathsf{NP}-complete.

Proof

To show that CLIQUE\text{CLIQUE} is NP\mathsf{NP}-complete, we have to show that it is in NP\mathsf{NP} and it is NP\mathsf{NP}-hard. Exercise (CLIQUE is in NP\mathsf{NP}) asks you to show that CLIQUE\text{CLIQUE} is in NP\mathsf{NP}, so we will show that CLIQUE\text{CLIQUE} is NP\mathsf{NP}-hard by presenting a reduction from 3SAT\text{3SAT} to CLIQUE\text{CLIQUE}.

Our reduction will be a Karp reduction. Given an instance of 3SAT\text{3SAT}, i.e. a Boolean formula φ\varphi, we will construct an instance of CLIQUE\text{CLIQUE}, G,k\langle G, k \rangle where GG is a graph and kk is a number, such that φ\varphi is a Yes instance of 3SAT\text{3SAT} (i.e. φ\varphi is satisfiable) if and only if G,k\langle G, k \rangle is a Yes instance of CLIQUE\text{CLIQUE} (i.e. GG contains a kk-clique). Furthermore, this construction will be done in polynomial time.

Let φ=(a1b1c1)(a2b2c2)(ambmcm),\varphi = (a_1 \vee b_1 \vee c_1) \wedge (a_2 \vee b_2 \vee c_2) \wedge \cdots \wedge (a_m \vee b_m \vee c_m), where each aia_i, bib_i and cic_i is a literal, be an arbitrary 3SAT formula. Notice that φ\varphi is satisfiable if and only if there is a truth assignment to the variables so that each clause has at least one literal set to True. From this formula, we build a graph GG as follows. For each clause, we create 3 vertices corresponding to the literals of that clause. So in total the graph has 3m3m vertices. We now specify which vertices are connected to each other with an edge. We do not put an edge between two vertices if they correspond to the same clause. We do not put an edge between xix_i and ¬xi\neg x_i for any ii. Every other pair of vertices is connected with an edge. This completes the construction of the graph. We still need to specify kk. We set k=mk = m.

As an example, if φ=(x1¬x2x3)(¬x1x2x3)(x1x1¬x1)\varphi = (x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_1 \vee \neg x_1), then the corresponding graph is as follows:

image

We now prove that φ\varphi is satisfiable if and only if GG has a clique of size mm. If φ\varphi is satisfiable, then there is an assignment to the variables such that in each clause, there is at least one literal set to True. We claim that the vertices that correspond to these literals form a clique of size mm in GG. It is clear that the number of such vertices is mm. To see that they form a clique, notice that the only way two of these vertices do not share an edge is if they correspond to xix_i and ¬xi\neg x_i for some ii. But a satisfying assignment cannot assign True to both xix_i and ¬xi\neg x_i.

For the other direction, suppose that the constructed graph GG has a clique KK of size mm. Since there are no edges between two literals if they are in the same clause, there must be exactly one vertex from each clause in KK. We claim that we can set the literals corresponding to these vertices to True and therefore show that φ\varphi is satisfiable. To see this, notice that the only way we could not simultaneously set these literals to True is if two of them correspond to xix_i and ¬xi\neg x_i for some ii. But there is no edge between such literals, so they cannot both be in the same clique.

This completes the correctness of the reduction. We still have to argue that it can be done in polynomial time. This is rather straightforward. Creating the vertex set of GG is clearly polynomial-time since there is just one vertex for each literal of the Boolean formula. Similarly, the edges can be easily added in polynomial time as there are at most O(m2)O(m^2) many of them.

Note

When we want to show that a language BB is NP\mathsf{NP}-hard, we take a known NP\mathsf{NP}-hard language AA and show a Karp reduction from AA to BB. The diagram of a typical transformation is as shown below.

image

So typically, the transformation does not cover all the elements of BB, but only a subset BBB' \subset B. This means that the Karp reduction not only establishes that BB is NP\mathsf{NP}-hard, but also that BB' is NP\mathsf{NP}-hard.

Theorem (IS is NP\mathsf{NP}-complete)

IS\text{IS} is NP\mathsf{NP}-complete.

Proof

To show that IS\text{IS} is NP\mathsf{NP}-complete, we have to show that it is in NP\mathsf{NP} and it is NP\mathsf{NP}-hard. Exercise (IS is in NP\mathsf{NP}) asks you to show that IS\text{IS} is in NP\mathsf{NP}, so we show that IS\text{IS} is NP\mathsf{NP}-hard. By Theorem (CLIQUE is NP\mathsf{NP}-complete), we know that CLIQUE\text{CLIQUE} is NP\mathsf{NP}-hard, and by Theorem (CLIQUE reduces to IS) we know that CLIQUEmPIS\text{CLIQUE}\leq_m^P\text{IS}. By the transitivity of reductions, we conclude that IS\text{IS} is also NP\mathsf{NP}-hard.

Note (Overview of reductions)

The collection of reductions that we have shown can be represented as follows:

image

Exercise (MSAT is NP\mathsf{NP}-complete)

The MSAT problem is defined very similarly to SAT (for the definition of SAT, see Definition (Boolean satisfiability problem)). In SAT, we output True if and only if the input CNF formula has at least one satisfying truth assignment to the variables. In MSAT, we want to output True if and only if the input CNF formula has at least two distinct satisfying assignments.

Show that MSAT is NP\mathsf{NP}-complete.

Solution

Showing MSAT is in NP\mathsf{NP}: To show that MSAT is in NP\mathsf{NP}, we need to show that there is a polynomial time verifier TM VV and tNt \in \mathbb N such that:

  1. if xMSATx \in \text{MSAT}, then there is some uu, uxt|u| \leq |x|^t, such that V(x,u)V(x,u) accepts;

  2. if x∉MSATx \not \in \text{MSAT}, then for all uu, V(x,u)V(x,u) rejects.

We present the verifier.

def    V(CNF formula F,  u):1.    If u does not correspond to two distinct 0/1 assignments to the variables in F, reject.2.    If both assignments in u satisfy F, accept.3.    Else, reject.\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; V(\langle \text{CNF formula } F \rangle, \; u ):\\ &{\scriptstyle 1.}~~~~\texttt{If $u$ does not correspond to two distinct $0/1$ assignments to the variables in $F$, reject.}\\ &{\scriptstyle 2.}~~~~\texttt{If both assignments in $u$ satisfy $F$, accept.}\\ &{\scriptstyle 3.}~~~~\texttt{Else, reject.}\\ \hline\hline\end{aligned}

The verifier is polynomial time: Checking whether uu a valid encoding of two distinct 0/1 assignments to the input variables can be done in polynomial time. Given a 0/1 assignment to the input variables, we can plug those values into the input CNF formula, and evaluate the output of the formula. This can be done in polynomial time. Since every step can be done in polynomial time, the verifier has polynomial time complexity.

Correctness: If xMSATx \in \text{MSAT}, then xx must a valid encoding of a CNF formula FF. Furthermore, FF must be such that there are at least two distinct 0/1 assignments to the input variables that make FF evaluate to 1. When uu is the encoding of such two distinct 0/1 assignments, the verifier will accept as desired. Note that clearly for such a uu, uO(F)|u| \leq O(|F|), i.e., the proof is polynomial in the length of FF. If x∉MSATx \not \in \text{MSAT}, then either xx is not a valid encoding of a CNF formula (in which case the verifier rejects, which is done implicitly since the input is not of the correct type), or xx is a valid encoding of a CNF formula, but there is at most one 0/1 assignment to the input variables that makes the formula output 1. In the latter case, if uu is not the encoding of two distinct 0/1 assignments, we reject. And if it is, then the last step detects that at least one of these 0/1 assignments makes the formula output 0, and so the verifier rejects again, as desired.

Showing MSAT is NP\mathsf{NP}-hard: To show that MSAT is NP\mathsf{NP}-hard, we show a Karp reduction from SAT (which we know is NP\mathsf{NP}-hard because we have shown 3SAT is NP\mathsf{NP}-hard) to MSAT. To show the Karp reduction, we need to show that there is a polynomial-time computable function f:ΣΣf : \Sigma^* \to \Sigma^* such that xSATx \in \text{SAT} if and only if f(x)MSATf(x) \in \text{MSAT}. Here is the function.

def    f(CNF formula F):1.    Let z be a variable name not included in F.2.    F=F(z¬z).3.    Return F.\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; f(\langle \text{CNF formula } F \rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Let $z$ be a variable name not included in $F$.}\\ &{\scriptstyle 2.}~~~~\texttt{$F' = F \wedge (z \vee \neg z)$.}\\ &{\scriptstyle 3.}~~~~\texttt{Return $\langle F' \rangle$.}\\ \hline\hline\end{aligned}

Polynomial time: It is pretty clear that each step above can be carried out in polynomial time (with respect to the length of FF).

Correctness: Suppose xSATx \in \text{SAT}. Then x=Fx = \langle F \rangle for some satisfiable CNF formula FF. Let y1,,yny_1,\ldots, y_n be the variables in FF. And suppose y1=b1,,yn=bny_1 = b_1, \ldots, y_n = b_n is a satisfying assignment for FF, where bi{0,1}b_i \in \{0,1\} for all ii. Then observe that both y1=b1,,yn=bn,z=0y_1 = b_1, \ldots, y_n = b_n, z = 0 and y1=b1,,yn=bn,z=1y_1 = b_1, \ldots, y_n = b_n, z = 1 are satisfying assignments for FF', and so FMSAT\langle F' \rangle \in \text{MSAT}. For the converse, assume FMSAT\langle F' \rangle \in \text{MSAT}. This means F=(F(z¬z))=(FTrue)F' = (F \wedge (z \vee \neg z)) = (F \wedge \text{True}) is satisfiable, which implies FF must satisfiable. So x=FSATx = \langle F \rangle \in \text{SAT}.

Exercise (BIN is NP\mathsf{NP}-complete)

In the PARTITION problem, we are given nn non-negative integers a1,a2,,ana_1,a_2,\ldots, a_n, and we want to output True if and only if there is a way to partition the integers into two parts so that the sum of the two parts are equal. In other words, we want to output True if and only if there is a set S{1,2,,n}S \subseteq \{1,2,\ldots, n\} such that iSai=j{1,,n}\Saj\sum_{i \in S} a_i = \sum_{j \in \{1,\ldots,n\} \backslash S} a_j.

In the BIN problem we are given a set of n items with non-negative sizes s1,s2,,snNs_1, s_2, \ldots , s_n \in \mathbb N (not necessarily distinct), a capacity C0C \geq 0 (not necessarily an integer), and an integer kNk \in \mathbb N. We want to output True if and only if the items can be placed into at most kk bins such that the total size of items in each bin does not exceed the capacity CC.

Show that BIN is NP\mathsf{NP}-complete assuming PARTITION is NP\mathsf{NP}-hard.

Solution

Showing BIN is in NP\mathsf{NP}: To show that BIN is in NP\mathsf{NP}, we need to show that there is a polynomial time verifier TM VV and tNt \in \mathbb N such that:

  1. if xBINx \in \text{BIN}, then there is some uu, uxt|u| \leq |x|^t, such that V(x,u)V(x,u) accepts;

  2. if x∉BINx \not \in \text{BIN}, then for all uu, V(x,u)V(x,u) rejects.

We now present the verifier. Below, s1,s2,,sns_1,s_2,\ldots, s_n and kk are non-negative integers and CC is a non-negative real.

def    V(s1,s2,,sn,C,k,  u):1.    If k>n, set k=n.2.    If u does not correspond to a partition (B1,B2,,Bk) of {1,2,,n}, reject.3.    If for some j{1,2,,k}, iBjsi>C, reject.4.    Else, accept.\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; V(\langle s_1,s_2,\ldots,s_n, C, k \rangle, \; u ):\\ &{\scriptstyle 1.}~~~~\texttt{If $k > n$, set $k = n$.}\\ &{\scriptstyle 2.}~~~~\texttt{If $u$ does not correspond to a partition $(B_1,B_2,\ldots, B_k)$ of $\{1,2,\ldots, n\}$, reject.}\\ &{\scriptstyle 3.}~~~~\texttt{If for some $j \in \{1,2,\ldots, k\}$, $\sum_{i \in B_j} s_i > C$, reject.}\\ &{\scriptstyle 4.}~~~~\texttt{Else, accept.}\\ \hline\hline\end{aligned}

The verifier is polynomial time: (First note that the nn in the question does not denote the input length. When we say “polynomial time”, it is with respect to the input length, which is s1,s2,,sn,C,k+u|\langle s_1,s_2,\ldots,s_n,C,k \rangle| + |u|.) Checking that uu is a partition of {1,,n}\{1,\ldots,n\} into kk parts, we need to check that there are kk sets, their union is {1,,n}\{1,\ldots,n\}, and that they are pair-wise disjoint. All of these can be easily checked in polynomial time. In the 3rd step, we implicitly have a loop that repeats knk \leq n times. In each iteration, we do at most nn additions, which is polynomial time in the input length (even if the sis_i’s are super big, note that they are part of the input and contribute to the length; addition is polynomial time).

Correctness: If xBINx \in \text{BIN}, then first, it must be a valid encoding. Furthermore, there must be a partition (B1,,Bk)(B_1,\ldots,B_k) of {1,,n}\{1,\ldots, n\} such that for each j=1,...,kj = 1,...,k, iBjsiC\sum_{i \in B_j} s_i \leq C (this is true by the definition of the problem). When uu represents such a partition, the verifier correctly accepts. Such a uu has length polynomial in nn, and therefore polynomial in the input length, as desired.

If x∉BINx \not \in \text{BIN}, then either xx is an invalid encoding (in which case the verifier rejects, which is done implicitly since the input is not of the correct type), or xx is a valid encoding, but there is no way to partition the elements into kk bins (B1,,Bk)(B_1, \ldots, B_k) such that iBjsiC\sum_{i \in B_j} s_i \leq C for all bins. If uu does not correspond to a partition (B1,,Bk)(B_1, \ldots, B_k), then we reject. And if it does, we successfully reject on the 3rd step. This completes the correctness argument.

Showing BIN is NP\mathsf{NP}-hard: To show that BIN is NP\mathsf{NP}-hard, we show a Karp reduction from PARTITION to BIN. To show the Karp reduction, we need to show that there is a polynomial time computable function f:ΣΣf : \Sigma^* \to \Sigma^* such that xPARTITIONx \in \text{PARTITION} if and only if f(x)BINf(x) \in \text{BIN}.

We now present ff. Below a1,a2,,ana_1,a_2,\ldots, a_n are non-negative integers.

def    f(a1,a2,,an):1.    Let si=ai for all i.2.    Let T=i{1,2,,n}si.3.    Let C=T/2.4.    Let k=2.5.    Return s1,s2,,sn,C,k.\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; f(\langle a_1,a_2,\ldots,a_n \rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Let $s_i = a_i$ for all $i$.}\\ &{\scriptstyle 2.}~~~~\texttt{Let $T = \sum_{i \in \{1,2,\ldots, n\}} s_i$.}\\ &{\scriptstyle 3.}~~~~\texttt{Let $C = T/2$.}\\ &{\scriptstyle 4.}~~~~\texttt{Let $k = 2$.}\\ &{\scriptstyle 5.}~~~~\texttt{Return $\langle s_1,s_2,\ldots, s_n,C,k \rangle$.}\\ \hline\hline\end{aligned}

Polynomial time: Addition and division are polynomial time operations and we only do these operations polynomially many times. So the whole function is polynomial time computable.

Correctness: If xx is in PARTITION, then x=a1,a2,,anx = \langle a_1,a_2,\ldots,a_n \rangle for non-negative integers aia_i, and there is S{1,,n}S \subset \{1,\ldots,n\} such that iSai=j{1,,n}\Saj\sum_{i \in S} a_i = \sum_{j \in \{1,\ldots,n\} \backslash S} a_j. Let T=i{1,,n}aiT = \sum_{i \in \{1,\ldots,n\}} a_i be the total sum. Then we must have iSai=j{1,,n}\Saj=T/2.\sum_{i \in S} a_i = \sum_{j \in \{1,\ldots,n\} \backslash S} a_j = T/2. If we let B1=SB_1 = S and B2={1,,n}\SB_2 = \{1,\ldots,n\} \backslash S, we see that the elements can be partitioned into two bins of capacity T/2T/2. Therefore the output f(x)f(x) is indeed an element of BIN.

For the other direction, if the output of the reduction f(x)f(x) is an element of BIN, then there is a way to partition the elements s1=a1,,sn=ans_1 = a_1,\ldots,s_n = a_n into k=2k = 2 bins B1B_1 and B2B_2 (B1B2={1,,n}B_1 \cup B_2 = \{1,\ldots,n\}, B1B2=B_1 \cap B_2 = \varnothing) of capacity C=T/2=12i{1,,n}siC = T/2 = \frac{1}{2} \sum_{i \in \{1,\ldots,n\}} s_i. Since the total sum of the elements is TT and each element must be in one of the two bins, the two bins must be completely full, i.e., iB1ai=T/2\sum_{i \in B_1} a_i = T/2 and jB2aj=T/2\sum_{j \in B_2} a_j = T/2. If we let S=B1S = B_1, then {1,,n}\S=B2\{1,\ldots,n\} \backslash S = B_2 and so iSai=j{1,,n}\Saj\sum_{i \in S} a_i = \sum_{j \in \{1,\ldots,n\} \backslash S} a_j. So x=a1,a2,,anx = \langle a_1,a_2,\ldots,a_n \rangle is indeed in PARTITION.

3
Check Your Understanding
Problem
  1. Informally, at a high-level, what does it mean for a language to be in NP\mathsf{NP}?

  2. Give an example of a language in NP\mathsf{NP} and at a high level explain why it is in NP\mathsf{NP}.

  3. What are the things you need to show in order to formally argue that a language LL is in NP\mathsf{NP}?

  4. Why is the complexity class NP\mathsf{NP} named “Non-deterministic polynomial time”?

  5. True or false: Every language in NP\mathsf{NP} is decidable.

  6. True or false: Any finite language is in NP\mathsf{NP}.

  7. True or false: {0,1}NP\{0,1\}^* \in \mathsf{NP}.

  8. True or false: {0k1k:kN}NP\{0^k1^k : k \in \mathbb N\} \in \mathsf{NP}.

  9. Explain why P\mathsf{P} is contained in NP\mathsf{NP}.

  10. True or false: If there is a polynomial-time algorithm for 3COL, then P=NP\mathsf{P}= \mathsf{NP}.

  11. True or false: HALTS is NP\mathsf{NP}-complete.

  12. Explain why NP\mathsf{NP} is contained in EXP\mathsf{EXP}.

  13. State the Cook-Levin Theorem and explain its significance.

  14. Let LΣL \subseteq \Sigma^*, and define its complement L={wΣ:w∉L}\overline{L} = \{w \in \Sigma^* : w \not\in L\}. Define coNP={LΣ:LNP}\textsf{coNP} = \{L \subseteq \Sigma^* : \overline{L} \in \mathsf{NP}\}. True or false: If coNPNP\textsf{coNP} \neq \mathsf{NP}, then PNP\mathsf{P}\neq \mathsf{NP}.

  15. True or false: If every language in NP\mathsf{NP} is NP\mathsf{NP}-complete (under Cook reductions) then P=NP\mathsf{P}= \mathsf{NP}.

  16. True or false: If P=NP\mathsf{P}= \mathsf{NP} then every language in NP\mathsf{NP} is NP\mathsf{NP}-complete (under Cook reductions).

  17. True or false: For any two NP\mathsf{NP}-complete languages AA and BB, there is a Cook reduction from AA to BB.

  18. True or false: Let L={0k1k:kN}L = \{0^k1^k : k \in \mathbb N\}. There is a Karp reduction from LL to 3COL.

  19. Assume PNP\mathsf{P}\neq \mathsf{NP}. Does 2COL Karp reduce to 3COL?

  20. Assume PNP\mathsf{P}\neq \mathsf{NP}. Does 3COL Karp reduce to 2COL?

4
High-Order Bits
Important Note
  1. Non-deterministic polynomial time is one of the most important definitions in the course. The formal definition is not easy to understand at first since it has several layers. Take your time to really digest it, and be careful with the order of quantifiers.

  2. When we ask you to show that a language is in NP\mathsf{NP}, we expect you to use the formal definition of NP\mathsf{NP}. Your proofs should resemble the proofs presented in this chapter.

  3. It is guaranteed that you will see an NP\mathsf{NP}-completeness proof in the homework and exam. In this course, your reductions establishing NP\mathsf{NP}-hardness must be Karp reductions. This chapter contains various such arguments, and we expect your own arguments to follow a similar structure. As usual, do not fall in the trap of memorizing templates. Focus on understanding why the proofs are structured the way they are.

Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (Non-deterministic polynomial time, complexity class \(\mathsf{NP}\))

Fix some alphabet \(\Sigma\). We say that a language \(L\) can be decided in non-deterministic polynomial time if there exists

  1. a polynomial-time decider TM \(V\) that takes two strings as input, and

  2. a constant \(k > 0\),

such that for all \(x \in \Sigma^*\):

  • if \(x \in L\), then there exists \(u \in \Sigma^*\) with \(|u| \leq |x|^k\) such that \(V(x,u)\) accepts,

  • if \(x \not \in L\), then for all \(u \in \Sigma^*\), \(V(x,u)\) rejects.

If \(x \in L\), a string \(u\) that makes \(V(x,u)\) accept is called a proof (or certificate) of \(x\) being in \(L\). The TM \(V\) is called a verifier for \(L\).

We denote by \(\mathsf{NP}\) the set of all languages which can be decided in non-deterministic polynomial time.

See in chapter
Definition (\(\mathcal{C}\)-hard, \(\mathcal{C}\)-complete)

Let \(\mathcal{C}\) be a set of languages containing \(\mathsf{P}\).

  • We say that \(L\) is \(\mathcal{C}\)-hard (with respect to Cook reductions) if for all languages \(K \in \mathcal{C}\), \(K \leq^PL\).
    (With respect to polynomial time decidability, a \(\mathcal{C}\)-hard language is at least as “hard” as any language in \(\mathcal{C}\).)

  • We say that \(L\) is \(\mathcal{C}\)-complete if \(L\) is \(\mathcal{C}\)-hard and \(L \in \mathcal{C}\).
    (A \(\mathcal{C}\)-complete language represents the “hardest” language in \(\mathcal{C}\) with respect to polynomial time decidability.)

See in chapter
Note (\(\mathcal{C}\)-hardness with respect to Cook and Karp reductions)

Above we have defined \(\mathcal{C}\)-hardness using Cook reductions. In literature, however, they are often defined using Karp reductions, which actually leads to a different notion of \(\mathcal{C}\)-hardness. There are good reasons to use this restricted form of reductions. More advanced courses may explore some of these reasons.

See in chapter
Theorem (Cook-Levin Theorem)

\(\text{CIRCUIT-SAT}\) is \(\mathsf{NP}\)-complete.

See in chapter
Proposition (3COL is in \(\mathsf{NP}\))

\(\text{3COL} \in \mathsf{NP}\).

See in chapter
Theorem (CIRCUIT-SAT reduces to 3COL)

\(\text{CIRCUIT-SAT}\leq_m^P3\text{COL}\).

See in chapter
Exercise (CLIQUE is in \(\mathsf{NP}\))

Show that \(\text{CLIQUE}\in \mathsf{NP}\).

See in chapter
Exercise (IS is in \(\mathsf{NP}\))

Show that \(\text{IS}\in \mathsf{NP}\).

See in chapter
Theorem (CLIQUE is \(\mathsf{NP}\)-complete)

\(\text{CLIQUE}\) is \(\mathsf{NP}\)-complete.

See in chapter
Theorem (CLIQUE reduces to IS)

\(\text{CLIQUE} \leq_m^P\text{IS}\).

See in chapter
Definition (Boolean satisfiability problem)

Let \(x_1,\ldots,x_n\) be Boolean variables, i.e., variables that can be assigned True or False. A literal refers to a Boolean variable or its negation. A clause is an “OR” of literals. For example, \(x_1 \vee \neg x_3 \vee x_4\) is a clause. A Boolean formula in conjunctive normal form (CNF) is an “AND” of clauses. For example, \[(x_1 \vee \neg x_3) \wedge (x_2 \vee x_2 \vee x_4) \wedge (x_1 \vee \neg x_1 \vee \neg x_5) \wedge x_4\] is a CNF formula. We say that a Boolean formula is a satisfiable formula if there is a truth assignment (which can also be viewed as a \(0/1\) assignment) to the Boolean variables that makes the formula evaluate to true (or \(1\)).

In the CNF satisfiability problem, the input is a CNF formula, and the output is True if and only if the formula is satisfiable. We denote this problem by \(\text{SAT}\). The corresponding language is \[\{\langle \varphi \rangle: \text{$\varphi$ is a satisfiable CNF formula}\}.\] In a variation of \(\text{SAT}\), we restrict the input formula such that every clause has exactly 3 literals (we call such a formula a 3CNF formula). For instance, the following is a 3CNF formula: For example, \[(x_1 \vee \neg x_3 \vee x_4) \wedge (x_2 \vee x_2 \vee x_4) \wedge (x_1 \vee \neg x_1 \vee \neg x_5) \wedge (\neg x_2 \vee \neg x_3 \vee \neg x_3)\] This variation of the problem is denoted by \(\text{3SAT}\).

See in chapter