The POST CORRESPONDENCE PROBLEM is defined as follows: You are given a collection of dominos. Each domino has a string of characters on top and another string on the bottom. (Both strings are non-empty.) You can make as many copies of the dominos as you need. The problem is to place the dominos side by side so that the combination of the strings on the top is the same as the combination of the strings on the bottom.
Example: Suppose domino D1 has string ``bbb" on top and string ``bb'' on bottom; domino D2 has strings ``a'' and ``bb'' and domino D3 has strings ``bb'' and ``bba''. Then the ordering D3, D2, D1, D1 spells out the string ``bbabbbbbb'' both on the top and on the bottom.
The Post correspondence problem is, surpringly, only semi-decidable. If there is an answer then, obviously, one can find it by exhaustive search; however, there is no algorithm that always terminates and that always answers correctly whether or not an instance of the problem has a solution.
empty --- D1 - bbb --- D1 - bbbbbb --- D1 - bbbbbbbbb --- D1 - bbbbbbbbbbbb empty | bb bbbb | bbbbbb | bbbbbbbb | | | | | |- D2 - bbbbbbbbba | | bbbbbbbb | | | |- D2 - bbbbbba | bbbbbb | |- D3 - bb --- D2 - bba --- D1 - bbabbb --- D1 - bbabbbbbb bba bbabb | bbabbbb bbabbbbbb | |- D3 - bbabb bbabbbba
Answer: The search goes into an infinite loop, exploring longer and longers strings with only D1.
empty --- D1 - bbb --- D1 - bbbbbb --- D1 - bbbbbbbbb --- D1 - bbbbbbbbbbbb empty bb bbbb | bbbbbb | bbbbbbbb | | | |- D2 - abbbbbbbbb | bbbbbbbb | |- D2 - abbbbbb --- D3 - bbabbbbbb bbbbbb bbabbbbbb
Answer: Depth (= maximum number of dominos in a string): KD. Branching factor: D. Size: At most O(DKD)