Reduction argument

Implement a machine computing the reduction function $f$ from the proof of Theorem 170 on p. 446 in the case of the alphabet $\Sigma =\left\{ a, b\right\}$.

Theorem 170: The problem $\mathrm{TOTAL}$ is undecidable.

Prove the algorithmic undecidability of the test-data completeness problem $\mathrm{TEST}$. The problem consists of triples $(\pi (\mathfrak {M}), x, q)$ such that the state $q$ occurs in the computation of the Turing machine $\mathfrak {M}$ on input $x$.

Prove the algorithmic undecidability of the zero problem $\mathrm{ZERO}$. The problem $\mathrm{ZERO}$ consists of codes $\pi (\mathfrak {M})$ of Turing machines $\mathfrak {M}$ such that $\mathfrak {M}(x)=\varepsilon$ for all $x$. Hint. Reduce $\mathrm{TOTAL}$ to $\mathrm{ZERO}$.

Prove the algorithmic undecidability of the following equivalence problem $\mathrm{EQU}$. The problem $\mathrm{EQU}$ consists of pairs $(\pi (\mathfrak {M}), \pi (\mathfrak {N}))$ such that the machines $\mathfrak {M}$ and $\mathfrak {N}$ are equivalent. Hint. Reduce $\mathrm{ZERO}$ to $\mathrm{EQU}$.

Prove the algorithmic undecidability of the test-data completeness problem $\mathrm{TEST}$. The problem consists of triples $(\pi (\mathfrak {M}), x, q)$ such that the state $q$ occurs in the computation of the Turing machine $\mathfrak {M}$ on input $x$.

Prove the algorithmic undecidability of the zero problem $\mathrm{ZERO}$. The problem $\mathrm{ZERO}$ consists of codes $\pi (\mathfrak {M})$ of Turing machines $\mathfrak {M}$ such that $\mathfrak {M}(x)=\varepsilon$ for all $x$. Hint. Reduce $\mathrm{TOTAL}$ to $\mathrm{ZERO}$.

Prove the algorithmic undecidability of the following equivalence problem $\mathrm{EQU}$. The problem $\mathrm{EQU}$ consists of pairs $(\pi (\mathfrak {M}), \pi (\mathfrak {N}))$ such that the machines $\mathfrak {M}$ and $\mathfrak {N}$ are equivalent. Hint. Reduce $\mathrm{ZERO}$ to $\mathrm{EQU}$.

Prove the algorithmic undecidability of the constant problem $\mathrm{CONST}$. The problem $\mathrm{CONST}$ consists of those $\pi (\mathfrak {M})$ such that the Turing machine $\mathfrak {M}$ returns the same result on any input, whenever it halts at all. Hint. Reduce the complement of $\mathrm{SELF}$ to $\mathrm{CONST}$.

Prove the algorithmic undecidability of the growth problem $\mathrm{GROW}$. The problem $\mathrm{GROW}$ consists of those $\pi (\mathfrak {M})$ such that the Turing machine $\mathfrak {M}$ computes an arithmetic function and $\mathfrak {M}(x)<\mathfrak {M}(y)$ holds for all $x<y$, whenever both values are defined. Hint. Reduce the complement of $\mathrm{SELF}$ to $\mathrm{GROW}$.

A set $A$ is called single-valued if for each $y$, there exists at most one $z$ such that $\langle y, z\rangle \in A$. Let $B_{12}=\left\{ x \mid W_{x}\text{ is single-valued }\right\}$. Show that EMP $\leq_{m} B_{12}$ and $B_{12} \leq_{m}$ EMP,

Assume that $A \leq_{m} B$ by a reduction function $f$ with time bound $2^{n}$. Also assume that $B \in \operatorname {DTIME}(2^{n})$. What can you say about the time complexity of set $A$?

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}$.

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}$.

Let $T=\left\{ \langle M\rangle \mid M \text{ is a TM that accepts } w^{\mathcal{R}} \text{ whenever it accepts } w\right\}$. Show that $T$ is undecidable.

ᴬ Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape when it is run on input $w$. Formulate this problem as a language and show that it is undecidable.

ᴬ Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.

Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.

A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any useless states. Formulate this problem as a language and show that it is undecidable.

Consider the problem of determining whether a Turing machine $M$ on an input $w$ ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.

Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma =\left\{ 0,1\right\}$.

Let $X=\left\{ \langle M, w\rangle \mid M\text{ is a single-tape TM that never modifies the portion of the tape that contains the input }w\right\}$. Is $X$ decidable? Prove your answer.

ᴬ Let $(\mathcal{N},<)$ be the model with universe $\mathcal{N}$ and the "less than" relation. Show that $\operatorname {Th}(\mathcal{N},<)$ is decidable.

ᴬ Let HALF-CLIQUE $=\left\{ \langle G\rangle \mid G \text{ is an undirected graph having a complete subgraph with at least } m / 2 \text{ nodes, where } m \text{ is the number of nodes in } G\right\}$. Show that HALF-CLIQUE is NP-complete.

A cut in an undirected graph is a separation of the vertices $V$ into two disjoint subsets $S$ and $T$. The size of a cut is the number of edges that have one endpoint in $S$ and the other in $T$. Let

Show that MAX-CUT is NP-complete. You may assume the result of Problem 7.26. (Hint: Show that $\neq S A T \leq_{\mathrm{P}}$ MAX-CUT. The variable gadget for variable $x$ is a collection of $3 c$ nodes labeled with $x$ and another $3 c$ nodes labeled with $\bar{x}$, where $c$ is the number of clauses. All nodes labeled $x$ are connected with all nodes labeled $\bar{x}$. The clause gadget is a triangle of three edges connecting three nodes labeled with the literals appearing in the clause. Do not use the same node in more than one clause gadget. Prove that this reduction works.)

A subset of the nodes of a graph $G$ is a dominating set if every other node of $G$ is adjacent to some node in the subset. Let

Show that it is NP-complete by giving a reduction from VERTEX-COVER.