2.1 The Circuit Satisfiability Problem (CIRCUIT-SAT)

Problem description. \[\textrm{CIRCUIT-SAT} = \{\langle C \rangle : C \textrm{ is a satisfiable boolean combinational circuit}\}\]

Lemma 2.1. \(\textrm{CIRCUIT-SAT} \in \mathrm{NP}\).

Proof sketch. Construct a two-input, polynomial-time algorithm \(\mathcal{A}\) such that for each logic gate in the circuit, it checks that the value provided by the certificate on the output wire is correctly computed as a function of the values on the input wires. If the output of the entire circuit is 1, \(\mathcal{A}\) outputs 1; otherwise \(\mathcal{A}\) outputs 0. Thus, we can verify CIRCUIT-SAT using the algorithm \(\mathcal{A}\) in polynomial time, therefore \(\textrm{CIRCUIT-SAT} \in \mathrm{NP}\).

■

Lemma 2.2. \(\textrm{CIRCUIT-SAT}\) is NP-hard.

Proof sketch. To show that any language \(L \in \mathrm{NP}\) is polynomial-time reducible to CIRCUIT-SAT, we must construct a polynomial-time algorithm computing some function \(f\) such that \[x \in L \iff f(x) \in \textrm{CIRCUIT-SAT}\]

Since \(L \in \mathrm{NP}\), there is a polynomial-time algorithm \(\mathcal{A}\) such that \[L = \{x \in \{0,1\}^* : \textrm{there exists } y \in \{0,1\}^* \textrm{ with } |y|=\mathcal{O}(|x|^c) \textrm{ such that } \mathcal{A}(x,y)=1\}\]

Given string \(x\), we build a circuit \(C(x)\) such that it consists of all the configuration steps of computing \(\mathcal{A}(x,y)\); we assign a set of input wires (which corresponds to string \(y\)) to \(C(x)\), which must satisfy each configuration step in order for the whole circuit to output 1. Since \(\mathcal{A}\) runs in polynomial time, we have \(\mathcal{O}(|x|^k)\) configuration steps, thus the whole circuit \(C(x)\) can also be computed in polynomial time; as long as it holds that \(\mathcal{A}(x,y)=1\) for some \(y\), the circuit is satisfied and outputs 1. Thus, we can ensure that \(C(x)\) has a satisfying assignment of input wires if and only if \(\mathcal{A}(x,y)=1\) for some \(y\) with \(|y|=\mathcal{O}(|x|^c)\).

Now that \(C(x)\) can be computed from \(x\) in polynomial time, \(L \leq_\mathrm{p} \textrm{CIRCUIT-SAT}\). Thus, CIRCUIT-SAT is NP-hard.

■

Theorem 2.3. \(\textrm{CIRCUIT-SAT} \in \mathrm{NPC}\).

Proof. It follows directly from Lemma 2.1 and Lemma 2.2 that \(\textrm{CIRCUIT-SAT} \in \mathrm{NPC}\).

■

Lemma 2.4. If \(L\) is a language such that \(L' \leq_\mathrm{p} L\) for some \(L' \in \mathrm{NPC}\), then \(L\) is NP-hard. If in addition \(L \in \mathrm{NP}\), then \(L \in \mathrm{NPC}\).

Proof. Since \(L'\) is NP-complete, for all \(L'' \in \mathrm{NP}\), we have \(L'' \leq_\mathrm{p} L'\). As \(L' \leq_\mathrm{p} L\) and by transitivity, we have \(L'' \leq_\mathrm{p} L\), which shows that \(L\) is NP-hard. If \(L \in \mathrm{NP}\), we have \(L \in \mathrm{NPC}\).

■

Lemma 2.4 provides with an important methodology for proving the NP-completeness of a language. Intuitively, if we can reduce a known NP-complete language \(L'\) to \(L\), we implicitly reduce every language in \(\mathrm{NP}\) to \(L\) (i.e., \(L\) is NP-hard). Therefore, to prove that \(L\) is NP-complete, we only need to:

1. Prove that \(L \in \mathrm{NP}\).
2. Prove that \(L\) is NP-hard by reducing a known NP-complete language \(L'\) to \(L\).
   1. Choose a known NP-complete language \(L'\).
   2. Construct an algorithm \(\mathcal{A}\) that computes a function \(f\) mapping every instance \(x\) of \(L'\) to an instance \(f(x)\) of \(L\).
   3. Prove that the function \(f\) satisfies \(x \in L'\) if and only if \(f(x) \in L\) for all \(x\).
   4. Prove that the algorithm \(\mathcal{A}\) runs in polynomial time.

2.2 The Formula Satisfiability Problem (SAT)

Problem description. \[\textrm{SAT} = \{\langle \phi \rangle : \phi \textrm{ is a satisfiable boolean formula}\}\]

Lemma 2.5. \(\textrm{CIRCUIT-SAT} \leq_\mathrm{p} \textrm{SAT}\).

Proof sketch. For each gate in the circuit \(C\), we construct a sub-formula \(\phi_i\) which is a logical equivalence of the operation on input wires and the output wire, e.g., for a certain gate, given the operation on input wires \(x_1 \lor x_2\) and the output wire \(x_5\), we construct the sub-formula \(\phi_i = x_5 \leftrightarrow (x_1 \lor x_2)\). We define the formula \(\phi = x_m \land \phi_1 \land \phi_2 \dots \land \phi_k\) (where \(x_m\) is the final output wire), which can be computed in polynomial time. If the circuit \(C\) has a satisfying assignment, then each wire of the circuit has a well-defined value (which is guaranteed by the sub-formula \(\phi_i\)), and the output of the circuit is 1. Thus, the circuit \(C\) is satisfiable exactly when the formula \(\phi\) is satisfiable. Therefore, \(\textrm{CIRCUIT-SAT} \leq_\mathrm{p} \textrm{SAT}\).

■

Theorem 2.6. \(\textrm{SAT} \in \mathrm{NPC}\).

Proof sketch. \(\textrm{SAT} \in \mathrm{NP}\) is trivially proved by constructing a verification algorithm that replaces each variable in the formula with its corresponding value and then evaluates the expression. If the expression evaluates to 1, then the algorithm has verified that the formula is satisfiable. Clearly, the verification algorithm runs in polynomial time.

To prove that \(\mathrm{SAT}\) is NP-hard, we show that \(\textrm{CIRCUIT-SAT} \leq_\mathrm{p} \textrm{SAT}\), as proved in Lemma 2.5. By the conclusion of Lemma 2.4, we have that \(\textrm{SAT} \in \mathrm{NPC}\).

■

2.3 The 3-CNF Satisfiability Problem (3-CNF-SAT)

Lemma 2.7. \(\textrm{SAT} \leq_\mathrm{p} \textrm{3-CNF-SAT}\).

[TBD]

2.4 The Clique Problem (CLIQUE)

Lemma 2.8. \(\textrm{3-CNF-SAT} \leq_\mathrm{p} \textrm{CLIQUE}\).

[TBD]

2.5 The Vertex-Cover Problem (VERTEX-COVER)

Lemma 2.9. \(\textrm{CLIQUE} \leq_\mathrm{p} \textrm{VERTEX-COVER}\).

[TBD]

2.6 * The Hamiltonian-Cycle Problem (HAM-CYCLE)

[TBD]

2.7 The Traveling-Salesman Problem (TSP)

Lemma 2.10. \(\textrm{HAM-CYCLE} \leq_\mathrm{p} \textrm{TSP}\).

[TBD]

2.8 The Subset-Sum Problem (SUBSET-SUM)

Lemma 2.11. \(\textrm{3-CNF-SAT} \leq_\mathrm{p} \textrm{SUBSET-SUM}\).

[TBD]