Partial Solutions

In Example 9.14 we used a technique for analyzing PCP instances that comes up frequently. We considered what the possible partial solutions were, that is, sequences of indexes 1,2,...,ir such that one of tfjjj Wjj Wi and Xi - Xj is a prefix of the other, although the two strings are not equal. Notice that if a sequence of integers is a solution, then every prefix of that sequence must be a partial solution. Thus, understanding what the partial solutions are allows us to argue about what solutions there might be.

Note, however, that because PCP is undecidable, there is no algorithm to compute all the partial solutions. There can be an infinite number of them, and worse, there is no upper bound on how different the lengths of the strmgs WiiWi Wi and XiXi Xi can be, even though the partial solution leads to a solution.

is the solution. Also, unlike PCP, where the solution has to have at least one integer on the solution list, in MPCP, the empty list could be a solution if wi - xi (but those instances are rather uninteresting and will not figure in our use of MPCP).

Example 9.15 : The lists of Fig, 9.12 may be regarded as an instance of MPCP. However, as an instance of MPCP it has no solution. In proof, observe that any partial solution has to begin with index 1, so the two strings of a solution would begin:

A: I---B: 111---

The next integer could not be 2 or 3, since both W2 and begin with 10 and thus would produce a mismatch at the third position. Thus, the next index would have to be 1, yielding:

A: 11---

B: mill---

We can argue this way indefinitely. Only another 1 in the solution can avoid a mismatch, but if we can only pick index 1, the В string remains three times as long as the A string, and the two strings can never become equal. □

An important step in showing PCP is undecidable is reducing MPCP to PCP. Later, we show MPCP is undecidable by reducing L to MPCP. At that point, we will have a proof that PCP is undecidable as well; if it were decidable, then we could decide MPCP, and thus Lu.

Given an instance of MPCP witli alphabet E, we construct an instance of PCP as follows. First, we introduce a new symbol * that, in the PCP instance, goes between every symbol in the strings of the MPCP instance. However, In the strings of the A list, the *s follow the symbols of E, and in the В list, the *s precede the symbols of E. Tho one exception is a new pair that is based on the first pair of the MPCP instance; this pair has an extra ж at the beginning of wi, so it can be u.sed to start the PCP solution. A final pair (*, *$} is added to the PCP instance. This pair serves as the last in a PCP solution that mimics a solution to the MPCP instance.

Now, let us formalize the above construction. We are given an instance of MPCP with lists A = wi,W2, .-,Wk and В = х\ ,Х2;.. Xk- We assume * and $ are symbols not present in the alj)habet £ of this MPCP instance. We construct a PCP instance С = Уо,У\., ,Ук+1 and D = zo,Z] ,...,Zk+i, as follows:

1. For г = 1,2,fc, let 1/i be uij with a * after each symbol of to;, and let Zi be Xi with a * before each symbol of xi.

2. уо - *yi; and Zq = z\. That is, the 0th pair looks like pair 1, except that there is an extra * at the beginning of the string from the first list. Note that the 0th pair will be the only pair in the PCP instance where both strings begin with the same symbol, so any solution to this PCP instance will have to begin with index 0.

3. J/jt+i - $ and Zk.y\ =

Example 9,16: Suppose Fig. 9.12 is an MPCP instance. Then the instance of PCP constructed by the above steps is shown in Fig. 9.14. □

Figure 9.14: Constructing an instance of PCP from an MPCP instance

Theorem 9.17: MPCP reduces to PCP.

PROOF: The construction given above is the heart of the proof. First, suppose that , 2,..., то is a solution to the given MPCP instance with lists A and B. Then we know wyWiWi. ivi, - x-xi-Xi -Xi. If we were to replace the

ws by ys and the жз by zs, we would have two strings that were almost the same: yiyiyt J/j and Zj, Zi г The difference is that the first string would be missing a * at the beginning, and the second would be missing a * at the end. That is,

However, = Щ\, and Zq - zi, so we can fix the initial * by replacing the first index by 0. We then have:

УоУпУ Vi =zoZijZi--- Zi *

We can take care of the final * by appending the index A; + 1. Since yk+\ = S, and - *S, we have:

УчУч Уь-- У1 Ук.+1 = ZQZiZi., Zi zki

We have thus shown that 0,ii,i2, - - ,im, A; + 1 is a solution to the instance of PCP.

Now, we must show the converse, that if the constructed instance of PCP has a solution, then the original MPCP instance has a solution as well. We observe that a solution to the PCP instance must begin with index 0 and end with index A: + 1, since only the 0th pair has strings уо and that begin with the same symbol, and only the (Ат+ l)st pair has strings that end with the same symbol. Thus, the PCP solution can be written 0,ii, J2i ?A; + 1.

We claim that , ia .., is a solution to the MPCP instance. The reason is that if we remove the *s and the final % from the string yoyi,yh УгУк+г we get the string wxw i Also, if we remove the *s and S from the string ZQZiZi we get xiXiXi We know that

yoyhyh --yiyk+i = ZoZi.Zi Zizk+i

so it follows that

Thus, a solution to the PCP instance impbes a solution to the MPCP instance.

We now see that the construction described prior to this theorem is an algorithm that converts an instance of MPCP with a solution to an instance of PCP with a solution, and also converts an instance of MPCP with no solution to an instance of PCP with no solution. Thus, there is a reduction of MPCP to PCP, which confirms that if PCP were decidable, MPCP would also be decidable. □

9.4.3 Completion of the Proof of PCP Undecidability

We now complete the chain of reductions of Fig. 9.11 by reducing L to MPCP. That is, given a pair (M, w), we construct an instance (.4, B) of MPCP such that TM M accepts input vi if and only if (Л, B) has a solution.