Reduction of one problem to another¶

definitions and interesting examples are yet to come

{exercise}
The *Pointed PCP Problem* (PPCP) is like Post's Correspondence Problem (PCP) except we have a designated domino $d_0$ which must be used as the first domino in a match. 

Let $PCP$ be the set of PCP instances for which there exists a match, and let $PPCP$ be the set of PPCP instances for which there is a match.

(a) Prove that $PPCP \leq_m PCP$.

(b) Prove that $PCP \leq_m PPCP$.

{exercise}
Suppose we consider a version of the tiling problem.
We are again given a pointed tile set.  But instead of tiling the first quadrant we only need to tile the "positive $x$-axis".  Let's call this problem $Tile_1$.
Show that $Tile_1$ is decidable.

{exercise}
Yet another version of tiling.  Given a pointed tile set, can we tile *the bottom two rows* of the quadrant?   Let's call this problem $Tile_2$.   Show that $Tile_1 \leq_m Tile_2$, and also that 
$Tile_2 \leq_m Tile_1$.

{exer}
Suppose we are given two finite domino sets, say $\DD_1$ and $\DD_2$.  

(a) Show that there is a domino set $\DD$ with the property that 
$\DD$ has a match if and only if both $\DD_1$ and $\DD_2$ have matches, and moreover that $\DD$ may be obtained computably from $\DD_1$ and $\DD_2$.

(b) Show that there is a domino set $\DD$ with the property that 
$\DD$ has a match if and only if either $\DD_1$ or $\DD_2$ have matches (or both), and moreover that $\DD$ may be obtained computably from $\DD_1$ and $\DD_2$.

{exercise}
Let $P_3$ be the matrix mortality problem for $3\times 3$ matrices.  Let $P_2$ and $P_4$ be defined similarly, for the $2\times 2$ and $4\times 4$ matrices.   Show that $P_2 \leq P_3 \leq P_4$.  This is a straightforward algebraic argument.

Later we will see that $P_4 \leq P_3$, but the argument will not be not as straightforward.