5 of 5
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/

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

vzn
  • 11k
  • 1
  • 27
  • 50