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

  • $\begingroup$ We don't always answer questions like this, which show absolutely no effort, but it seems you were lucky this time. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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