Distributional Post Correspondence

The distributional Post correspondence problem was shown to be complete for DistNP by Gurevich [Gur91]. A simplified proof was given in [WB95] and will be presented here. For convenience, for a list , we call the -list of , and the -list of . Let denote the set of all positive instances of the problem. Recall that denotes the uniform probability distribution on instances of the bounded Post correspondence problem.

A negative instance does not prevent from having a solution of length greater than . We say that an instance is robust if either has a solution of length at most or does not have solutions at all.

Proof.simplicity, we use the standard nondeterministic one-tape single-headed Turing machines as our computation model. The tape is bounded on the left and unbounded to the right. At the initial state, the input is left justified on the tape and the head is positioned at the leftmost symbol of the input.

Let be a distributional problem in DistNP. Then there is a (nondeterministic) Turing machine which accepts in polynomial time. Without loss of generality, we assume that all the computation paths of are bounded by a polynomial of the length of inputs. By the Distribution Controlling Lemma , there is a total, one-one, p-time computable and p-time invertible function such that for all . Let .

We now construct a Turing machine with only one halting state. takes input and determines whether for some . If is not defined, then goes into an infinite loop state, otherwise, simulates on . halts when on reaches an accepting state. If on reaches a rejecting state, then simply goes into an infinite loop state.

It is easy to see that for all , the length of each ID of on input is bounded by a fixed polynomial of , and on input halts (has a halting computation) if and only accepts . Moreover, on input halts if and only if it halts within steps for some fixed polynomial .

Let be the halting state of , the initial state of , the blank symbol, the set of states of , and the transition function of . Let . Let . Fix a dynamic binary coding system for and the finite set . We know that the length of a coded symbol is . For any word on , we use to denote its coded word of . So is the string obtained from by replacing with and with .

Let be an instance of the distributional Post correspondence problem comprising the following pairs of binary strings.

1. (Group I) .

2. (Group II) for , and is obtained from by replacing with and with .

3. (Group III) for each .

4. (Group IV) For each and ,

   

5. (Group V) , , for .

6. (Group VI) .

A pair is a partial solution to the distributional Post correspondence problem with list if is a prefix of , and and are the concatenation of corresponding strings of -list and -list respectively. If , then call the remainder of .

Let be a string of coded symbols in . Denote by the string obtained from by replacing each coded symbol with and with the last omitted. Suppose from initial ID there is a valid sequence of more ID's. Let denote an ID in a usual way. We claim that there is a partial solution
.
Moreover, this is the only type of partial solution whose larger string is as long as . Since the length of each ID is bounded by a fixed polynomial of , it is a partial solution of length bounded by times a polynomial of .

It is obvious that any solution must start with . To continue, the only choice now is from pairs in Group II because of the coding system we used. This gives the correspondence of to . Then the only pair that can be applied is . This gives a partial solution . So this verifies the case when . By a simple induction and the coding scheme we used, one can easily prove the statement. For completeness, we present its proof below.

Suppose that the statement is true for some and that . We can easily show that it is true for . The remainder of the pair is . The next pairs must be chosen so that their strings from the -list form . No matter what symbols appear to the right and left of , it will take a pair from Group IV to enable the partial solution to be continued past . This pair represents, in a natural way, a move of from ID . Use choices from Group III for other symbols of . No other choices will enable to be composed of elements in the -list. We can thus obtain a new partial solution . It is straightforward to see that is an ID that can reach on one move from . Also, there are no other partial solutions whose length of the second string equals . Since each ID is bounded by a polynomial of , the length of this partial solution is bounded by times a polynomial of . In addition, if , then is bounded by a polynomial of . It is easy to find pairs from Groups III and V which, when preceded by the partial solution and followed by the pair in Group VI, provide a solution of length bounded by a polynomial of to . If does not reach the halting state, no pairs from Groups V and VI may be used. Therefore, there may be partial solutions, but the second string must exceed the first string, so no solution is possible.

We conclude that has solution if and only if on input halts. We know that on input halts if and only if on input halts within steps. So if has a solution, then it has a solution bounded by a polynomial of . So there is a polynomial such that on input halts if and only has a solution of length at most .

Let . It is easy to see that is a robust instance. Notice that . Clearly, is one-one and p-time computable. Moreover, is reducible to via . Now we verify that . Since and any other string in has length , where , it is easy to see that for some polynomial . Hence, .

In the proof of Theorem 5.1, if we let be a new list by omitting (Group I) from the list and reversing the order of every remaining pair, then iff is a positive instance of the distributional string correspondence problem. Moreover, it is straightforward to verify that the reduction defined by satisfies the domination requirement. This provides a proof to the following theorem.

Gurevich [Gur91] showed that the distributional palindrome problem is complete for DistNP by reducing a restriction of the distributional Post correspondence problem to the problem. An instance of the Post correspondence problem is called palindrome sensitive if there is no palindrome such that , where belongs to . As a corollary of the proof of Theorem 5.1, it is straightforward to show the following lemma.

Proof.will reduce the palindrome sensitive version of the distributional Post correspondence problem to the distributional palindrome problem. Given a palindrome sensitive instance and a positive integer , the desired reduction produces a grammar with productions , and number . The domination requirement is obvious. We need to check that has a solution of length iff produces a nonempty palindrome in at most steps.

It is clear that every solution for gives rise to a -step derivation of the palindrome . Suppose that produces a nonempty palindrome in steps. Since is palindrome sensitive, . This completes the proof.