PCP with commutative alphabet

Question

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?

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.