NP-Completeness

Sat is in NP.

Formulate the following puzzle as a Boolean formula $F$, and solve it by determining whether $F$ is satisfiable:

With five games left in the regular season, the team mathematician reported to the manager of the baseball team A: "We can still make the playoffs if we can beat team $B$, and in case team $B$ beats team $C$ then team $C$ beats team $D$, and in case we lose to team $C$ then team $D$ also beats either team $B$ or team $C$." Later, among the remaining five games, each team won at least one game, but no team won all its remaining games, and there was no tie game. Did team A have any chance to make the playoffs? If so, how?

Formulate the following puzzle as a Boolean formula $F$, and solve it by determining whether $F$ is satisfiable:

Three men named Lewis, Miller, and Nelson fill the positions of accountant, cashier, and manager in the leading department store in the City of NP. The following information about their jobs is known:

• If Nelson is the cashier, Miller is the manager.

• If Nelson is the manager, Miller is the accountant.

• If Miller is not the cashier, Lewis is the manager.

• If Lewis is the accountant, Nelson is the manager.

What is each man's job?

Hamiltonian Cycle (HC): Given a graph $G$, determine whether $G$ has a Hamiltonian cycle.

HC is in NP.

(Knight's Tour) Find a tour of the $8 \times 8$ chessboard by a knight which visits each square exactly once and comes back to the starting square.

Vertex Cover (VC): Given a graph $G$ and a positive integer $k$, determine whether $G$ has a vertex cover of size at most $k$.

VC is in NP.

Hitting Set (HS): Given subsets $A_{1}, A_{2}, \ldots , A_{n}$ of a set $S$ and an integer $k$, determine whether there is a subset $A \subseteq S$ of size $\left|A\right| \leq k$ such that $A \cap A_{i} \neq \emptyset$ for all $i=1, \ldots , n$.

HS is in NP.

Formulate the following logical puzzle as an instance of the problem HS and solve it by finding the correct subset.

Three women, Joan, Michelle, and Tracy, made the following statements about their ages.

Joan: "I am 92 years old. I am two years younger than Michelle. I am one year older than Tracy." Michelle: "I am not the youngest. I am three years different from Tracy. Tracy is 25 years old." Tracy: "I am younger than Joan. Joan is 23 years old. Michelle is three years older than Joan." If we know that, among three statements given by each person, exactly two are true. What are their ages?

IS is in NP.

(Eight-Queen Problem) Place eight queens in an $8 \times 8$ chessboard without them attacking each another. (In the chess game, a queen attacks another piece if they are located in the same row, or in the same column, or in the same diagonal.)

3DM is in $\mathrm{NP}$.

IP is in $\mathrm{NP}$.

Formulate the following logical puzzle as an instance of the problem IP, and solve it by solving the corresponding system of inequalities.

Professor $X$ presented a colloquium talk in the Department of Complexity. When he started to talk, he noticed that the 15 people of the audience satisfy the following conditions:

• There were more students than professors.

• There were more male professors than male students.

• There were more male students than female students.

• There was at least one female professor.

Five minutes later, a person rushed into the room. However, the appearance of this person did not change the above four conditions. Is this person a man or a woman, a student or a professor?

Prime is in NP.

Prove that 683 is a prime.

For any set $A$, let $A^{\prime }=\left\{ w \# 0^{n} \mid w\text{ is a suffix of some }x\text{ in }A\text{ with }\left|x\right|=n\right\}$ and $A^{\prime \prime }=\left\{ w \mid w\text{ has a suffix }x\text{ in }A\right\}$. Show that if $A$ is in NP, then $A^{\prime }$ and $A^{\prime \prime }$ are also in $\mathrm{NP}$.

For any set $B \subseteq \left\{ 0,1\right\}^{*} \# \left\{ 0,1\right\}^{*}$, let $\operatorname {prefix}(B)=\left\{ x \# u \mid x, u \in \left\{ 0,1\right\}^{*},\left(\exists v \in \left\{ 0,1\right\}^{*}\right) x \# u v \in B \right\}$.

A function $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ is polynomial-time computable if there is a polynomial-time DTM that computes the function $f$ (i.e., on input $x$, it halts in $p(|x|)$ moves for some polynomial $p$, with the string $f(x)$ on the output tape). A function $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ is polynomially honest if there is a polynomial function $p$ such that $|f(x)| \leq p(|x|)$ and $|x| \leq p(|f(x)|)$ for all $x \in \left\{ 0,1\right\}^{*}$. Assume that $f$ is polynomial-time computable and is polynomially honest.

Formulate the following puzzles as instances of problems in NP, and then solve the puzzles by finding the witnesses to the instances:

The threshold function $T_{n, k}$ is a Boolean function defined as follows:

Prove that the following integers are primes: $293,587,65537,214177$.

Show that the following problems are in NP:

Let $A$ be an $n \times n$ integer matrix, and $b$ an $n$-dimensional integer vector. Let $\alpha$ be the maximum absolute value of integers in $A$ and $b$, and $q= \max \left\{ m, n\right\}$.

HC $\leq_{m}^{P} \mathrm{LP}$.

$\mathrm{VC} \equiv_{m}^{P}$ IS.

GIso $\equiv_{m}^{P}$ DGIso.

SAT $\leq_{m}^{P}$ CNF-SAT.

$\mathrm{VC} \leq_{m}^{P} \mathrm{IP}$.

$3\mathrm{DM} \leq_{m}^{P} \mathrm{SAT}$.

$3\mathrm{SAT} \leq_{m}^{P} \mathrm{VC}$.

$3\mathrm{SAT} \leq_{m}^{p} \mathrm{HC}$.

Prove that CNF-Sat $\leq_{m}^{P}$ 3Sat.

In this exercise, we study an alternative proof for Example 7.25. Let us replace conditions (1) and (2) by condition (3): For every $a \in A \cup B \cup C$, there is a triple $w \in W^{\prime }$ such that (i) $a \in w$, and (ii) if $w^{\prime } \in W^{\prime }, w^{\prime } \neq w$ then $a \notin w^{\prime }$. Translate this condition into a Boolean formula $G$ over variables $x_{w}$ and show that $G$ is satisfiable if and only if $W$ has a threedimensional matching $W^{\prime }$.

Construct the following reductions:

Consider the following variations of the problem 3Sat:

3Sat-Exactly-One: Given a 3-CNF $F$, determine whether there is an assignment $t$ on variables in $F$ that assigns value TRUE to exactly one literal in each clause of $F$.

3Sat-Not-All: Given a 3-CNF $F$, determine whether there is an assignment $t$ on variables in $F$ that assigns value TRUE to either one or two literals (but not all three literals) in each clause of $F$.

Show that 3Sat, 3Sat-Exact-One and 3Sat-Not-All are polynomial time equivalent under $\leq_{m}^{P}$.

Consider the following problems: Subgraph Isomorphism (SGIso): Given two graphs $G_{1}= \left(V_{1}, E_{1}\right)$ and $G_{2}=\left(V_{2}, E_{2}\right)$, determine whether there is a one-to-one mapping $f: V_{1} \rightarrow V_{2}$ such that, for all $u, v \in V_{1}$, $\left\{ u, v\right\} \in E_{1}$ implies $\left\{ f(u), f(v)\right\} \in E_{2}$.

Graph Automorphism (GAuto): Given a graph $G= (V, E)$, determine whether there is a one-to-one function $f: V \rightarrow V$ other than the identity function such that, for all $u, v \in V,\left\{ u, v\right\} \in E$ if and only if $\left\{ f(u), f(v)\right\} \in E$.

Prove all the polynomial-time reductions you can find among the three problems GIso, SGIso and GAuto.

Show that if $P=\mathrm{NP}$, then all nonempty proper subsets $A$ of $\Sigma^{*}$ are NP-complete.

If $A$ is known to be $\mathrm{NP}$-complete, is $A^{2}$ always $\mathrm{NP}$-complete?

In the proof of Cook's theorem, we have used conditions (4.1) $-(4.5)$ on ???-shaped windows over matrix $S$ to satisfy condition (4). Show that if we, instead, work with ???-shaped windows over matrix $S$, then no conditions on these windows can satisfy condition (4). In other words, show that the following relation does not hold for any subset $T \subseteq \left(\Gamma^{\prime }\right)^{4}$ :

where $\alpha_{i}$ denotes the $i$ th configuration corresponding to the assignments to variables $y_{i, j, a}$.

Show that, in the proof of Cook's theorem, function $f_{1}$ is necessary. That is, no definition of subset $T$ can make the following true: $F_{x}^{\prime }=f_{0} f_{2} f_{3} f_{4}$ is satisfiable if and only if $x \in L(M)$.

In the proof of Cook's theorem, it is possible to remove condition (1), as long as we replace condition (4') by a new condition (4'') over six-square, ???-shaped windows. Find the subconditions over the six-square, ???-shaped windows that make $\left(4^{\prime \prime }\right)$ equivalent to condition (4), without the assumption of condition (1).

A Boolean formula which is a product of literals is called an elementary product. A DNF (disjunctive normal form) is a sum of elementary products.

Assume that $A$ and $B$ are two $\mathrm{NP}$-complete sets. Show that $A \cup B$ and $A \cap B$ are not necessarily $\mathrm{NP}$-complete, if $P \neq \mathrm{NP}$. Is $A \cup B$ always $\mathrm{NP}$-complete when $A \cap B=\emptyset$?

This exercise follows the notations defined in Exercise 3 of Section 7.1.

Assume that $P \neq \mathrm{NP}$. Let $A$ and $B$ be two sets that are complete for $c o-\mathrm{NP}$ (i.e., $\bar{A}$ and $\bar{B}$ are NP-complete). Is $A B$ necessarily in co-NP? Is $A B$ necessarily co-NP-complete? Is it possible that $A B$ is in $P$? Justify your answer.

Suppose that, in the proof of Cook's theorem, we drop condition (1) and replace condition $\left(4^{\prime }\right)$ by $(\overline{4})$, which specifies some subconditions on five-square windows of one of the four shapes shown in Figure 7.11. Show that no such subconditions on the five-square windows can make (4) equivalent to $\left(4^{\prime }\right)$.

Consider the alternative proof of Cook's theorem given in Example 7.33. Let $T \subseteq \left(\Gamma^{\prime }\right)^{6}$ be the set corresponding to the twelve windows of Figure 7.10; that is, $(a, b, c, d, e, g) \in T$ if and only if $(a, b, c, d, e, g)$ is in one of the twelve forms in Figure 7.10, and satisfies the corresponding conditions given in the three cases. Show that if there exists a mapping $\phi :\left(\Gamma^{\prime }\right)^{3} \rightarrow \left(\Gamma^{\prime }\right)^{3}$ such that $(a, b, c, d, e, g) \in T$ if and only if $\phi (a, b, c)= (d, e, g)$, then $L(M)$ is in $P$.

In this exercise, we consider a different setting for the proof of Cook's theorem. Instead of attaching the state symbol to the tape symbol currently scanned by the tape head, we may define separate Boolean variables to represent the state and the position of the tape head. That is, in addition to variables $y_{i, j, a}$ (for $a \in \Gamma$ only), we define, for each $i=0, \ldots , r(n)$ and each $q \in Q$, a variable $Q_{i, q}$ to mean that the state symbol of $\alpha_{i}$ is $q$, and for each pair $(i, j)$, with $i, j \in \left\{ 0, \ldots , r(n)\right\}$, a variable $H_{i, j}$ to mean that, in the configuration $\alpha_{i}$, the tape head is scanning the $j$ th symbol. To prove Cook's theorem in this setting, then we need to define six Boolean functions $g_{1}, \ldots , g_{6}$, such that, for $k=1, \ldots , 6, g_{k}=1$ if and only if the condition $(k)$ below holds:

(1) For each $i=0, \ldots , r(n), \alpha_{i}$ is in exactly one state.

(2) For each $i=0, \ldots , r(n)$, the head scans exactly one cell in $\alpha_{i}$.

(3) For each $i=0, \ldots , r(n)$ and each $j=0, \ldots , r(n)$, the $j$ th cell of $\alpha_{i}$ contains exactly one symbol.

(4) $\alpha_{0}$ is the initial configuration of $M$ on input $x$.

(5) $\alpha_{r(n)}$ is an accepting configuration.

(6) For each $i=0, \ldots , r(n)-1, \alpha_{i} \vdash \alpha_{i+1}$.

Assume that $g_{1}, \ldots , g_{5}$ satisfy the condition that $g_{k}=1$ if and only if condition $(k)$ holds. Also let $g_{6}$ be

where $\Delta =-1$ if $D=L$, and $\Delta =1$ if $D=R$. Find a counterexample to disprove that $G_{x}=\prod_{i=1}^{6} g_{i}=1$ if and only if $M$ accepts $x$. Find a new function $g_{6}$ satisfying that $G_{x}=1$ if and only if $M$ accepts $x$.

Does the problem VC remain NP-complete if each edge is to be covered by exactly one vertex?

Prove that MCG is NP-complete.

Partition is NP-complete.

Knapsack is NP-complete.

BP is NP-complete.

Show that the following problem is NP-complete: Given positive integers $a_{1}, \ldots , a_{n}$, determine whether

SMT is NP-complete.

For each of the following problems, determine whether it is $\mathrm{NP}$-complete or is in $P$. If it is $\mathrm{NP}$-complete, find a reduction from a known $\mathrm{NP}$ complete problem to it. If it is in $P$, find a polynomial-time algorithm for it.

Prove that the following variations of the problem VC are $\mathrm{NP}$-complete:

The polar representation of a CNF $F$ is a bipartite graph $G_{F}= \left(V_{1}, V_{2}, E\right)$, where $V_{1}$ is the set of all variables and $V_{2}$ is the set of all clauses in $F$, and there is an edge in $E$ between $x_{i} \in V_{1}$ and $c_{j} \in V_{2}$ if and only if the variable $x_{i}$ appears in the clause $c_{j}$ (in the form of $x_{i}$ or $\bar{x}_{i}$). Prove the following statements:

The nonpolar representation of a CNF $F$ is a graph $G_{F}=(V, E)$, with the vertex set $V$ consisting of all literals and all clauses in $F$, and the edge set $E$ consisting of all pairs $\left\{ x, \bar{x}\right\}$ over all variables $x$ in $F$ plus all literal-clause pairs $\left\{ z, c\right\}$ such that $z$ occurs in $c$. Prove the following statements:

A $(k, \ell )-C N F F$ is a CNF such that each clause contains exactly $k$ literals and each variable occurs in at most $\ell$ clauses. The problem $(k, \ell )$-Sat is the problem 3SaT restricted to $(k, \ell )$-CNF's. Prove the following results:

Show that Min-VC is an NP-complete search problem.

TSP is NP-complete.

The problem $r$-Approx-TSP is NP-complete for all $r>1$.

The problem $r$-Approx-VC is NP-complete for some $r>1$.

For each $d \geq 3$, the problem $r$-Approx-VC- $d$ is NP-complete for some $r>1$.

For $1<r<\sqrt{2}$, $r$-Approx-BST is NP-complete.

For each of the following search problems, formulate an appropriate decision version of it and show that the decision version and the search version are equivalent under polynomial-time Turing reduciblity.

For each of the following optimization problems, show that it is NPcomplete:

Show that for each of the following optimization problems II, there exists an approximation ratio $r>1$ such that $r$-Approx- $\Pi$ is $\mathrm{NP}$-complete.

For a graph $G$, its edge-square graph $G^{2}$ is a graph obtained from $G$ by replacing each edge $\left\{ u, v\right\}$ by a copy of $G$, called $G_{u, v}$, and connecting both $u$ and $v$ to every vertex in $G_{u, v}$.

Show that for each of the following optimization problems $\Pi$, there exists a constant $\varepsilon >0$ such that $n^{\varepsilon }$-Approx- $\Pi$ is $\mathrm{NP}$-complete.