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)

up vote 4 down vote accepted

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.

[1] Tackling Posts correspondence problem by Zhao (v2?)

[2] A polynomial reduction from any NP-complete problem to bounded PCP, cs.se

[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

[8] Creating Difficult Instances of the Post Correspondence Problem by Lorentz

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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