Reduction of one problem to another

definitions and interesting examples are yet to come

Exercise 11

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 12

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 13

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\).

Exercise 14

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.