# Decidable restrictions of the Post Correspondence Problem

The Post Correspondence Problem (PCP) is undecidable.

The bounded version of the PCP is $\mathrm{NP}$-complete and the marked version of the PCP (the words of one of the two lists are required to differ in the first letter) is in $\mathrm{PSPACE}$ [1].

1. Are these restricted versions used to prove some complexity results of other problems (through reduction)?
2. Are there other restricted versions of the PCP that make it decidable (and in particular $\mathrm{PSPACE}$-complete)?

[1] "Marked PCP is decidable" by V. Halava, M. Hirvensalo, R. De Wolf (1999)

## 2 Answers

there is more than one way to "bound" PCP (maybe verging on many!) and there seems to be diverse research into many variants. limiting the number of concatenated blocks or total length of concatenated strings to a parameter specified on the input (specified in binary) appears to be NExpSpace complete but have not seen this written up in a paper. see Bounded Post Correspondence Problem NP-Complete Proof, tcs.se. if you limit the same "concatenation length" parameter to a polynomial of the input size its apparently PSpace complete. again havent seen that written up anywhere despite some search.

there is also somewhat related research into resolving special cases of the PCP (somewhat reminiscent of Busy Beaver research), see eg PCP solver by Zhao or [8]. note that theres also a remarkable/pioneering case of applying DNA computing for a somewhat-probabilistic approach.[3] also there seems to be more research by Halava[4],[7] into other decidable variants. [5,6] are further misc results.

[3] Using DNA to solve the Bounded Post Correspondence Problem by Kari et al

[4] On Post Correspondence Problem for Letter Monotonic Languages by Halava et al

[5] The Post correspondence problem over a unary alphabet by Rudnicki

[6] Post Correspondence Problem with Partially Commutative Alphabets Barbara Klunder, Wojciech Rytter

[7] Some New Results on Post Correspondence Problem and Its Modifications by Halava, Harju

Ehrenfeucht, Karhumäki and Rozenberg have shown that binary PCP (where the domain is binary) is decidable. Halava and Holub later showed that it's actually in P.