可判定的限制的职位的对应关系问题

Question

的 职位对应关系问题 (PCP)是无法判定的。

的 界版本的PCP 是$\mathrm{NP}$-完成 标记的版本PCP (话的两个清单需要不同于在第一个字母)是在$\mathrm{PSPACE}$[1].

1. 这些限制的版本用于证明一些复杂的结果的其他问题(通过减少)?
2. 是否还有其他限制版本的PCP，使它可判定的(和特别是$\mathrm{PSPACE}$完成的)?

[1] "标记PCP是可判定的"由V.Halava，M。Hirvensalo,R.De Wolf(1999年)

Answer 1

有超过一种方式"约束"PCP(也许近乎于许多!) 而且似乎是多样化的研究成许多变体。限制的数量级联块或总长度的串连串的参数指定的输入(指定在二)看起来是NExpSpace完成，但还没有看过这写在一张纸上。看看 界职位对应关系问题NP-完整的证据,tcs。se。如果限制相同的"串联的长度"的参数来的多项式的输入其大小显然PSpace完成。再没有见过这写在任何地方，尽管有一些搜索。

还有些相关研究为解决特殊情况下的PCP(有点让人联想到繁忙的海狸研究)，见例如： PCP解 赵或[8].请注意，世界上还有一个显着的/开拓性的情况下施用DNA计算有点-概率的方法。[3]也似乎有更多的研究Halava[4],[7]进入其他可判定的变体。[5,6]进一步misc的结果。

[1] 处理员额的对应关系问题 赵 (v2?)

[2] 多项式减少从任何NP-完整的问题，以界PCP, cs.se

[3] 使用DNA来解决的界后 对应关系问题 通过Kari et al

[4] 关于员额的对应关系问题的信的单调的语言 通过Halava et al

[5] 该员额的对应关系问题通过一元字母 通过Rudnicki

[6] 职位对应关系问题 部分可交换的字母 芭芭拉Klunder,Wojciech Rytter

[7] 一些新成果的后 对应关系问题和其 修改 通过Halava,Harju

[8] 创造困难的实例后对应关系问题 由洛仑兹

Answer 2

Ehrenfeucht，Karhumäki和Rozenberg表明二进制PCP（域是二进制的地方）是可决定的。 哈拉瓦和霍鲁布 后来表明它实际上在P中。