Post's Correspondence Problem is known to be undecidable. A variant of PCP, namely PCP with partially commutative alphabets is also known to be undecidable. Is the following variant also known to be undecidable?

PCP with commutative alphabet. Given and alphabet $\Sigma = \{a_1, a_2, \ldots, a_K\}$ and $2N$ sequences $\gamma_1, \gamma_2, \ldots, \gamma_N, \delta_1, \delta_2, \ldots, \delta_N \in \Sigma^*$. Determine if there is a sequence of integers $\{i_j\}_{j=1}^M$ such that for each $1 \leq j \leq M$, $i_j \in \{1, 2, \ldots, N\}$ and for each $1 \leq m \leq K$,

$\#(a_m, \gamma_{i_1} \gamma_{i_2} \ldots \gamma{i_M}) = \#(a_m, \delta_{i_1} \delta_{i_2} \ldots \delta_{i_M})$ where $\#(a, w)$ denotes the number of occurences of the symbol $a$ in the string $w$.

Notice why I used the term "commutative" for the alphabet: the order of the symbols in the strings does not matter; only the counts need to be equal.

In general, is any variant of (unbounded) PCP with commutative alphabet known to be decidable or undecidable?

  • $\begingroup$ In the paper you link it is mentioned (on page 358): "The only known (positive) result related to PCP with commutative alphabet is of [12] and deals with the Parikh equivalence, i.e. the case when the p.c. alphabet is fully commutative." $\endgroup$ Dec 18, 2018 at 12:46

1 Answer 1


Let $\gamma_{ij},\delta_{ij}$ be the number of characters $\sigma_j$ in $\gamma_i,\delta_i$ (respectively). Then the PCP instance has a solution if there exist non-negative integers $a_1,\ldots,a_N,b_1,\ldots,b_N$ such that for all $j \in \{1,\ldots,K\}$, $$ \sum_{i=1}^N a_i \gamma_{ij} = \sum_{i=1}^N b_i \delta_{ij}. $$

While integer programming is hard in the general case, in this case we can solve it using linear programming in polynomial time. I claim that the program above has a solution in non-negative integers iff it has a solution in non-negative reals. One direction is obvious. In the other direction, suppose that the linear program corresponding to the integer program above (replacing non-negative integers with non-negative reals) is feasible. Then there is a solution for the program above in the non-negative rationals (every vertex of the polytope would do). Multiplying this solution by a common denominator, we obtain a solution of the original integer program.


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.