The question is as follows:

Let's observe the following Post correspondence problem.

Input: Two finite lists of words $A$ and $B$ and a natural number $k$.

Question: Is there any words correspondence with a length of $k$ at the maximum?

Describe an algorithm to solve the problem and analyze its runtime.

I really don't understand how to solve this problem. From my understanding, the Post correspondence problem is undecidable so how come we can describe an algorithm to solve this question?


1 Answer 1


PCP is undecidable essentially because, if there is a match, it could be arbitrarily long. But, here, the question specifically excludes any string longer than $k$ characters. There are only about $2^{k+1}$ possible strings of length at most $k$ over alphabet $\{a,b\}$. Does that help you find an algorithm?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.