Reduction of one problem to another
Reduction of one problem to another¶
definitions and interesting examples are yet to come
Exercise 30
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 31
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 32
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\).