Reduction of one problem to another

Reduction of one problem to another#

definitions and interesting examples are yet to come

Proposition 2

Let \(A\leq B\).

If \(B\) is decidable, then so is \(A\).
If \(A\) is undecidable, then so is \(B\).

Exercises#

Tiling#

In the problems below on tiling, you should use the notion of reduction that we are currently studying.

Exercise 15

The one dimensional tiling problem is the problem of deciding whether a tile set can tile the “positive \(x\)-axis” part of the quadrant (the bottom infinite row). Show that this problem is decidable by reducing to the problem of whether a finite graph has a cycle.

Exercise 16

The two-row tiling problem is the same problem, but we want to tile the bottom-most two infinite rows. Is this problem decidable or undecidable?

Exercise 17

What about the two-column tiling problem?

Roots of polynomials#

Exercise 18

Let \(X\) be the set of multi-variable polynomials \(p(x_1, \ldots, x_n)\) with integer coefficients which have a root consisting of positive integers, and let \(Y\) be the polynomials with integer coefficients which have a root consisting of negative integers. Show that \(X \leq Y\) and \(Y\leq X\).

Post correspondence problem#

Exercise 19

Assuming that \(PCP\) is undecidable, show that it is undecidable even if the alphabet has only two letters.

Matrix mortality#

Exercise 20

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 easy.

Here is an exercise pertaining to the matrix mortality problem. Athough it looks long, we are presenting it as result in outlined form. All you have to do is to fill in the steps. This result will be used in our later work on the undecidability of matrix mortality.

Exercise 21

Let \(M_{1,1}\) be the set of finite sets of \(3\times 3\) integer matrices which have some finite product which equals \(0\). Let \(M_{0}\) be the set of finite sets of \(3\times 3\) integer matrices which have some finite product with \(0\) in the upper-left corner. In this exercise, we show that \(M_{1,1} \leq M_0\).

Let \(A\) be the \(3\times 3\) matrix

\[\begin{split} \left[ \begin{array}{lll} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right] \end{split}\]

The key features of \(A\) are shown below:

\[\begin{split} \left[ \begin{array}{lll} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right] \left[ \begin{array}{lll} a & b & c \\ d & e & f \\ g & h & i \end{array}\right] %\left[ \begin{array}{lll} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right] = \left[\begin{array}{lll} a & b & c \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right] \end{split}\]

We also have

\[\begin{split} \left[ \begin{array}{lll} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right] \left[ \begin{array}{lll} a & b & c \\ d & e & f \\ g & h & i \end{array}\right] \left[ \begin{array}{lll} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right] = \left[\begin{array}{lll} a & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right] \end{split}\]

Let \(Q\) be the set of finite sets of \(3\times 3\) integer matrices.

Here is a computable function \(f: Q \to Q\):

\[ f(S) = S\cup \{A\} \]

Our goal is to prove the following fact:

Let \(S\) be a finite set of \(3\times 3\) matricies.

Show that if \(S \in M_{1,1}\), then \(f(S) \in M_0\). [This is easy given the facts above.]
In the other direction, suppose that \(f(S) \in M_0\). Take a finite sequence from \(f(S)\) whose product has a zero in the upper-left corner. Write the product as

\[ A B^1_1 B^1_2 \cdots B^1_{n_1} A B^2_1 B^2_2 \cdots B^2_{n_1}\cdots A B^k_1 B^k_2 \cdots B^k_{n_k} A \]

where the \(B^i_j\) matrices belong to \(S\).

Divide the product above into \(k+1\) groups:

\[ (A B^1_1 B^1_2 \cdots B^1_{n_1}) \quad (A B^2_1 B^2_2 \cdots B^2_{n_1}) \quad\cdots\quad (A B^k_1 B^k_2 \cdots B^k_{n_k}) \quad A \]

And then multiply it group-by-group:

\[\begin{split} \left[\begin{array}{lll} a^1 & b^1 & c^1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right] \left[\begin{array}{lll} a^2 & b^2 & c^2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right] \cdots \left[\begin{array}{lll} a^k & b^k & c^k \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right] \left[\begin{array}{lll} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right] \end{split}\]

Here each \(a^i\) is the product of the \(i\)th group.

Evaluate the upper-left corner of the product, and check that one of the groups \( B^i_1 B^i_2 \cdots B^i_{n_i}\) must multiply to give a matrix with \(0\) in the upper-left corner.

Credits

The source for the reduction involving \(3\times 3\) matrices is

Vesa Halava and Tero Harju, (2001). Mortality in Matrix Semigroups. The American Mathematical Monthly, 108(7), 649–653.