Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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?
