Reduction of one problem to another

We are very interested in relations between problems. Here is the main definition that we will use.

Definition

Let \(S\) and \(T\) be well-defined sets of mathematical objects, and let \(A\subseteq S\) and \(B\subseteq T\) be problems. We do not assume that \(S\) or \(T\) is decidable. We write

\[ A \leq B \]

and say that \(B\) is at least as hard as \(A\), or that \(A\) is reducible to \(B\) if there is an intuitively computable \(t: S\to T\) such that for all \(x\),

\[ \mbox{$x\in A \quadiff t(x) \in B$} \]

We sometimes call \(t\) the translation map.

We are going to see a few examples of this soon. But first, here is the result that shows why we are interested in this definition in the first place.

Proposition 2

If \(A\leq B\) and \(B\) is intuitively decidable, then \(A\) is also intuitively decidable.

If \(A\leq B\) and \(A\) is intuitively undecidable, then \(B\) is also intuitively undecidable.

Proof. For the first part: given \(x\), to see if \(x\in A\) or not, apply the intuitively computable translation \(t\), and then see if \(t(x)\in B\) or not. The answer must be the same!

The second assertion follows from the first.

Incidentally, we read \(A\leq B\) as \(B\) is at least as hard as \(A\). However, there are situations where \(A\leq B\) according to our definition but where most people would say that \(A\) is much harder to decide.

Exercise 9

Let \(S\) and \(T\) be the set of natural numbers, let \(A\) be the set of prime numbers, and let \(B = \set{1,2,3}\). Show that according to our definitions \(A\leq B\). However, \(A\) and \(B\) are both intuitively decidable, and most people who know about such things would agree that \(A\) is harder than \(B\).

The moral of the story is that our English rendering of \(A\leq B\) is only good for comparisons of decidable vs. undecidable problems.

Example related to the PCP

Recall that the Post Correspondence Problem (PCP) is the set of finite domino sets which have a post word. We introduce a variant of this problem, the Modified PCP (MPCP): A pointed domino set is one that comes with a distinguished domino \(d^*\) called the start domino. Technically, it is a pair \((\mathcal{D},d^*)\), where \(d^*\in \DD\). The MPCP is the set of finite pointed domino sets which have a Post sequence starting with \(d^*\).

Proposition 3

\(MPCP \leq PCP\). That is, there is an intuitively computable translation function \(t: MPCP \to PCP\) such that each pointed domino system \((\mathcal{D},d^*)\), has a Post sequence iff its translation \(t(\mathcal{D},d^*)\) is an ordinary domino system which has a Post sequence.

Given an input to the MPCP, say \((\DD,d^*)\), take two new symbols, say \(\blacksquare\) and \(\$ \), and then define \(t(\DD,d^*)\) in the following way:

1. Add \(\blacksquare\) after all letters in all top words in the original domino set.

2. Add \(\blacksquare\) before all letters in all bottom words in the original domino set.

3. Add a new copy of the start domino, \(d^*\), but modify it by adding \(\blacksquare\) after all letters in the top and before all letters in the bottom, and also add \(\blacksquare\) before the first letter of the top word. This one is called the first special domino.

4. Add a new domino with top word \(\$ \) and bottom word \(\blacksquare\) \(\$ \). This last one is called the second special domino.

---

Note that we have a intuitively computable function \(f\) from pointed tile sets to tile sets. That is, adding the symbols \(\$ \) and \(\blacksquare\) like this is intuitively computable. In particular, we don’t need to know whether the original pointed domino set has a Post word or not in order to add the new symbols.

Example

Here is a pointed domino set \((\mathcal{D},d^*)\):

The green domino is \(d^*\). Here is the domino set \(t(\mathcal{D},d^*)\).

The two special dominoes are shown at the end.

Claim

If \(\DD\) has any Post sequence starting with \(d^*\), then \(t(\DD)\) has a Post sequence.

And if \(t(\DD)\) has a Post sequence, then \(\DD\) has one that starts with \(d^*\).

Proof. The first assertion is easier. If we have a Post sequence in the original \((\mathcal{D},d^*)\) with word \(w\), then we trade in these dominoes for the evident corresponding dominoes in \(t(\mathcal{D},d^*)\), except that we begin the first special domino. We also add the second special domino at the end. Then it is easy to see that we have a Post sequence in \(t(\mathcal{D},d^*)\): the word across the top and bottom is the same word \(w\) as above, except that we add \(\blacksquare\) before all the letters, and also at the end, and follow it with \(\$ \).

In the more challenging direction, suppose that \(t(\DD, d^*)\) has a Post sequence, then \(\DD\) has one that starts with \(d^*\). The main fact here is that a Post sequence for \(t(\DD)\) must start with the first special domino, since this is the only one whose top and bottom words start with the same symbol. It also has to end with the second special domino.

``

Exercise 10

Show that \(PCP \leq MPCP\). Here is what this means, spelled out. You need to define an intuitively computable function \(t\) from domino sets to pointed domino sets with the property that for all domino sets \(\DD\):

1. If \(\DD\) has a Post sequence, then \(t(\DD)\) has one also, and one that starts with the start domino of \(t(\DD)\).

2. Conversely, if \(t(\DD)\) has a Post sequence that starts with its start domino, then \(\DD\) has a Post sequence.

Why does \(t\) have to be intuitively computable?

Similarly, we can now say why our definition of \(A \leq B\) requires the translation function \(t: S\to T\) to be intuitively computable. If we took away this restriction, Proposition 2 would be false in general: consider the case when \(A\) is undecidable and \(B\) is decidable, and \(t\) is a constant function.

Examples related to integer roots of polynomials

We turn to some examples related to polynomials and systems of them. In this discussion, we are looking at polynomials in many variables with integer coefficients. Consider the following sets:

\[\begin{split} \begin{array}{lcl} A & = & \mbox{all polynomials which have an integer root}\\ A_{\leq 4} & = & \mbox{all polynomials of degree $\leq 4$ which have an integer root}\\ B & = & \mbox{all systems of polynomials which have a common integer root}\\ \end{array} \end{split}\]

As an example of an element of \(B\), consider

\[\begin{split} \begin{array}{l} 2x^2 - y \\ x^{449} -8y + wz \\ xyzw - 15 \end{array} \end{split}\]

One common root is \(x = 1\), \(y = 2\), \(z = 3\), \(w = 5\). There might be others, but it only takes one common root to put a system into \(B\).

Proposition 4

\(A \leq B\).

Every polynomial is a system with just one polynomial. So we may take the translation map \(t\) taking polynomials into systems to be the inclusion map.

Proposition 5

\(B \leq A\).

We need to exhibit an intuitively computable translation \(t\) from systems of polynomials to single polynomials with the property that

\[\begin{split}\begin{array}{cl} & \mbox{$(p_1,\ldots, p_k)$ has a common integer root}\\ \quadiff & \mbox{$t((p_1,\ldots, p_k))$ has an integer root}\\ \end{array} \end{split}\]

Let \(t\) be defined by

\[ \begin{array}{lcl} t((p_1,\ldots, p_k)) & = & \sum_{i=1}^k {p}_i^2 \end{array} \]

To see that this works, fix \(p_1,\ldots, p_k\) and let \(\overline{x} = x_1, \ldots, x_n\) be all the variables that occur in these polynomials. Then

\[\begin{split} \begin{array}{ll} & \mbox{$(p_1,\ldots, p_k)$ has a common integer root} \\ \mbox{iff} & (\exists x_1, \ldots, x_n\in\mathbb{Z}) \mbox{ for $i = 1, \ldots, k$}, p_i(\overline{x} ) = 0 \\ \mbox{iff} & (\exists x_1, \ldots, x_n\in\mathbb{Z}) \mbox{ for $i = 1, \ldots, k$}, p_i^{2}(\overline{x} ) = 0 \\ \mbox{iff} & (\exists x_1, \ldots, x_n\in\mathbb{Z}) {\sum_{i=1}^k} p_i^{2}(\overline{x} ) \ = 0 \\ \mbox{iff} & (\exists x_1, \ldots, x_n\in\mathbb{Z}) t(p_1,\ldots, p_k) (\overline{x}) = 0 \\ \mbox{iff} & t((p_1,\ldots, p_k)) \mbox{ has an integer root} \\ \end{array} \end{split}\]

This calculation shows that \(A\leq B\) via \(t\).

This is the most difficult of the verifications. We present an example and invite you to work out the full details as an exercise.

Consider

\[ \begin{array}{lcl} 4x^3 y^4 + 3y^3 - 13 z^5 & = & 0 \end{array} \]

Let’s introduce seven new variables: \(a\), \(b\), \(c\), \(d\), \(e\), \(f\), and \(g\). Then we make the linear system

\[\begin{split} \begin{array}{c} \begin{array}{lcl} a & = & x^2 \\ b & = &ax \\ \\ \end{array}\qquad \begin{array}{lcl} c & = & y^2 \\ d & = &c^2 \\ e & = & c y \\ \end{array}\qquad \begin{array}{lcl} f & = & z^2 \\ g & = & f^2 \\ h & = & gz \\ \end{array} \\ \\ \begin{array}{lcl} 4 bd + 3e - 13 h & = & 0 \\ \end{array} \end{array} \end{split}\]

This shows that \(A \leq B_2\), where \(E_2\) is the set of linear systems with roots. Then we compose with the function which we already saw which shows that \(B\leq A\). This turns the system above into a single equation of degree \(4\):

\[\begin{split} \begin{array}{lcl} (a - x^2)^2 + (b - ax)^2 + (c-y^2)^2 + (d - c^2)^2 + (e - cy)^2 & & \\ + (f- z^2)^2 + (g - f^2)^2 + (h-gz)^2 + (4 bd + 3e - 13 h )^2 & = & 0 \end{array} \end{split}\]

This transformation preserves satisfiability in \(\mathbb{Z}\) and shows that \(A \leq A_{\leq 4}\).

The method of introducing variables to make something simpler is sometimes called Skolem’s trick.

Exercises

Here are some exercises to help you get catch on. Some of these will be quite tricky, and the trickiness is due to two things: first, the definition of the translation function \(t\) often requires ingenuity and cleverness. Your first attempt might not be correct. That is, you might not be able to prove the required ‘if and only if’ statement; this itself might require a tricky argument.

Observation

In showing that \(t: S\to T\) works, the hard direction is often the one that “goes backwards”, saying: “if \(t(x)\in B\), then \(x\in A\).”

Tiling

Exercise 11

The one-row 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 12

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?

What about the two-column tiling problem?

Roots of polynomials

Exercise 13

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

Exercise 14

We presented an example of how \(A \leq A_4\) could work, but we didn’t really define a function that does this. Your task is to do this.

PCP

Exercise 15

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

Matrix mortality

Exercise 16

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. Although 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 17

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}\]

There are two key features of \(A\):

\[\begin{split} \begin{array}{rcl} \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] \\ \ \\ \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{array} \end{split}\]

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

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

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

Our goal is to prove the following fact:

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

1. Show that if \(S \in M_{1,1}\), then \(t(S) \in M_0\). [This is easy given the facts above.]

2. In the other direction, suppose that \(t(S) \in M_0\). Take a finite sequence from \(t(S)\) whose product has a zero in the upper-left corner. Let us assume that the sequence both begins and ends with \(A\). 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}\]

Figure out what each \(a^i\) represents in terms of the groups of matrices above.

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.