対応後の問題の決定可能な制限

cs.stackexchange https://cs.stackexchange.com/questions/701

質問

対応の問題を投稿します （PCP）は決定できません。

PCPの境界バージョン $ mathrm {np} $ - 完了し、 PCPのマーク付きバージョン （2つのリストの1つの単語は、最初の文字で異なるために必要です）は$ mathrm {pspace} $ [1]です。

  1. これらの制限されたバージョンは、他の問題の複雑さの結果を証明するために使用されていますか（削減による）？
  2. PCPの他の制限付きバージョンは、それを決定できるようにします（特に$ mathrm {pspace} $ - 完了）？

[1] "マークされたPCPは決定可能です"V. Halava、M。Hirvensalo、R。DeWolf（1999）

役に立ちましたか？

解決

PCPを「バインド」する方法は複数あり（多分多くを駆け巡る！）、多くのバリエーションに関する多様な研究があるようです。連結したブロックの数または連結された文字列の総長さを入力（バイナリで指定）で指定されたパラメーターに制限することは、Nexpspaceが完全であるように見えますが、これを論文に書いていません。見る 境界後の通信問題NP完全証明, 、Tcs.se。同じ「連結長」パラメーターを入力サイズの多項式に制限すると、明らかにPSPACEが完了します。繰り返しますが、検索にもかかわらずどこにでも書かれているのを見ていません。

PCPの特別なケースの解決に関する多少関連する研究もあります（忙しいビーバーの研究を幾分連想させる）、例： PCPソルバー Zhaoまたは[8]。やや公人アプローチのためにDNAコンピューティングを適用するという顕著な/先駆的なケースもあります。[3]また、他の決定可能なバリアントに関するHalava [4]、[7]によるより多くの研究があるようです。 [5,6]はさらにMISCの結果です。

[1] 投稿の対応の問題に取り組む zhao （V2？）

[2] NP完全な問題から境界のあるPCPへの多項式の減少, 、cs.se

[3] DNAを使用して、境界のある後の対応問題を解決します Kari et al

[4] 文字単調言語の対応後の問題について Halava et al

[5] 単一のアルファベット上のポスト通信の問題 Rudnickiによる

[6] 部分的に通勤するアルファベットの対応問題を投稿します バーバラ・クランダー、wojciech rytter

[7] 対応後の問題とその変更に関するいくつかの新しい結果 ハラバ、ハルジュ

[8] ポスト通信の問題の難しいインスタンスを作成します ローレンツによって

他のヒント

Ehrenfeucht、Karhumäki、およびRozenbergは、バイナリPCP（ドメインがバイナリである）が決定可能であることを示しています。 ハラバとホルブ 後でそれが実際にPにあることを示しました

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top