PCP when upper and lower words have different length The Post correspondence problem (PCP) asks, given two sets of words $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$ over the same alphabet, whether there are indices $i_1,\ldots,i_s \in \{1,\ldots,n\}$ and $j_1,\ldots,j_t \in \{1,\ldots,m\}$ such that
$$
a_{i_1} \ldots a_{i_s} = b_{j_1} \ldots b_{j_t}.
$$
It is well-known that PCP is undecidable.
What happens if we restrict $s \neq t$? Does the problem become any easier?
The problem doesn't become any easier.
Suppose we are given an instance $a_1,\ldots,a_n,b_1,\ldots,b_m$ of PCP.
Let $\sigma$ be a new symbol. Add to the first list the words $a'_1 = \sigma a_1,\ldots,a'_n = \sigma a_n$, and to the second list the word $b'_0 = \sigma$.
If the new PCP instance has a solution, then we can obtain a solution of the original PCP instance by removing all occurrences of $\sigma$. Now suppose that the original PCP instance has a solution
$$ a_{i_1} \ldots a_{i_s} = b_{j_1} \ldots b_{j_t}. $$
If $s \neq t$ then this is a solution of the new PCP instance in which $s \neq t$. If $s = t$, then consider the following solution instead:
$$ a'_{i_1} \ldots a_{i_s} = b'_0 b_{j_1} \ldots b_{j_t}. $$