I’m sure most people remember the “Post Correspondence Problem” from Theory of Computation classes. It’s mainly famous for two reasons:

- It’s the classic example of an undecidable problem that isn’t about a language (like the Halting Problem is)
- It leads to lots of fun (meaning “bad”) PCP jokes. (“I need some PCP to be able to handle thinking about the PCP”)

Anyway, here is a restricted version of the problem that at least is decidable, if intractable.

**The problem**: Bounded Post Correspondence Problem. This is problem SR11 in the appendix.

**The description**: Given two sequences of strings A = and B = from a finite alphabet, and a positive integer K, can I find a sequence of integers i_{1}..i_{k}, where k ≤ K, and the string A’= is identical to the string B’ =?

**Example: **The difference between this and “classic” PCP is the introduction of K, which makes the problem decidable because if nothing else you can just try all combinations of strings from A and B that are length K or less, which is finite.

So, any PCP instance that “works” is a good example to use here. Here’s one that I got from my old Hopcroft and Ullman theory of computation book:

A = {1, 10111,10} B = {111,10,0}

We can construct the string 101111110. From A, it’s built from 10111/1/1/10. From B, it’s built from 10/111/111/0

Notice that we need to use the same elements from each string in the sequence (The second one, then the first one twice, then the third one).

**Reduction: **The reference in G&J is to a technical report by Constable, Hunt, and Sahni and says they use a “generic transformation”. In the paper, that means they show it’s NP-Complete by showing it’s a “negation of freedom for a 2 variable loop free scheme” Which is, as near as I can tell, a way of defining programs to be equivalent.

I’ll admit that I don’t really understand it. I really want there to be a simpler reduction out there. I found this post on stackexchange, but it reduces from Shortest Common Supersequence, and uses a |R| of 2, and G&J say that Shortest Common Supersequence is polynomial with |R|=2, so something has to be wrong there.

I was tinkering with a reduction from Directed Hamiltonian Cycle, where the strings in A corresponded to edges, and the strings in B correspond to vertices. So, for a graph like this:

You would get strings like this:

A | B |

x | xa |

ab | bb |

bc | cc |

ca | a |

cd | dd |

The idea is that each string in A corresponds to a directed edge, and each string in B corresponds to 2 copies of the destination of that edge. The “x” is there to give us a starting point- we arbitrarily choose some starting vertex to be the start. All edges that have this starting vertex as its destination only have 1 copy (instead of 2) of that vertex in B.

The problem is that a string like xabbcca (corresponding to a non-Hamiltonian cycle) is a solution to the PCP problem, but is not a solution to the HC problem. I don’t know how to force the string to be long enough to visit all vertices- I thought about working on a variant of the problem where you force the size of the string you create to be exactly =K instead of ≤ K. But since a cycle that doesn’t involve the start vertex can be “pumped” several times to make a string longer, that won’t work either. There is probably something clever you can do with the strings to force you to visit all vertices, but I can’t see it.

**Difficulty: **10, sadly. I’m sure there is something easier out there.

Couldn’t one use the fact that the bounded halting problem is NP-hard, and a reduction from that to the bounded PCP? But maybe the standard reduction is not polynomial…

Hmm, I hadn’t run across the bounded halting problem before. Is it just given a program and a K, does the program halt in K steps?

Maybe you can do something similar to the proof that PCP is undecidable then. I’m not convinced that’s a whole lot easier though 🙂

Essentially, yes. For deterministic TMs, I think K has to be given in binary encoding, for nondeterministic TMs, unary seems to work, see e.g. here:

http://www.inf.ed.ac.uk/teaching/courses/cmc/lecture6.pdf

By the by, in Garey and Johnson, SR11, K is even restricted to K<=n, n being the number of string pairs.