# PCP is decidable over the unary alphabet

Show that the Post Correspondence Problem (PCP) is decidable over the unary alphabet ? = {0}.

• We don't always answer questions like this, which show absolutely no effort, but it seems you were lucky this time. – Yuval Filmus Jun 3 '18 at 18:23

I will use the following formalization: A PCP-instance is a set $X = \{(a_1, b_1), ..., (a_n, b_n)\}$ where $a_i, b_i \in \Sigma^\ast$ where $\Sigma = \{0\}$ is our alphabet (note that thus every $a_i, b_i$ is of the form $0^k$). Such an instance is a yes-instance if there exists a finite sequence $I \in \{1, ..., n\}^m$ such that $a_{I_1}...a_{I_m} = b_{I_1}...b_{I_m}$.
Now, obviously, if there exists a pair such that $a_i = b_i$, then we have a yes-instance and if $|a_i| < |b_i|$ (or, by symmetry, $|b_i| < |a_i|$) for all $i$, then the instance must be a no-instance. Otherwise, there exist $i \neq j$ such that $|a_i| < |b_i|$ and $|a_j| > |b_j|$ and note that the problem now boils down to finding $k_i, k_j \in \mathbb{N}$ such that $k_i \Delta_i = k_j \Delta_j$ where $\Delta_i = |b_i| - |a_i|$ and $\Delta_j = |a_j| - |b_j|$. But this equation clearly has a solution for all $(\Delta_i, \Delta_j) \in \mathbb{N}^2$ by simply choosing $k_i = \Delta_j$ and $k_j = \Delta_i$, giving us that $$a_i^{\Delta_j} a_j^{\Delta_i} = b_i^{\Delta_j} b_j^{\Delta_i}$$ as $|b_i^{\Delta_j}| - |a_i^{\Delta_j}| = \Delta_j (|b_i| - |a_i|) = \Delta_i \Delta_j$ and $|a_j^{\Delta_i}| - |b_j^{\Delta_i}| = \Delta_i (|a_j| - |b_j|) = \Delta_i \Delta_j$ and thus, \begin{align} |a_i^{\Delta_j} a_j^{\Delta_i}| - |b_i^{\Delta_j} b_j^{\Delta_i}| &= |a_i^{\Delta_j}| + |a_j^{\Delta_i}| - |b_i^{\Delta_j}| - |b_j^{\Delta_i}| \\ &= (|a_j^{\Delta_i}| - |b_j^{\Delta_i}|) - (|b_i^{\Delta_j}| -|a_i^{\Delta_j}|) \\ &= \Delta_i \Delta_j - \Delta_i \Delta_j\\ &= 0 \end{align}.
Hence, it suffices to check whether there exist $i, j$ such that $|a_i| \leq |b_i|$ and $|b_j| \leq |a_j|$ (output yes if this is the case and no otherwise) and it follows that the PCP over unary alphabets is decidable.