Zdecydowane ograniczenia problemu z korespondencją pocztową

Post Korespondencja Problem (PCP) jest nierozstrzygalny.

Ograniczoną wersją PCP jest -Complete i oznaczone wersja PCP (słowa jednego z obu listach muszą różnić się w pierwszej literze) jest P S P A C E [1].$\mathrm{NP}$$\mathrm{PSPACE}$

1. Czy te ograniczone wersje są wykorzystywane do udowodnienia, że ​​niektóre problemy są złożone (poprzez redukcję)?
2. Czy istnieją inne ograniczone wersje PCP, które sprawiają, że jest on rozstrzygalny (w szczególności Complete)?$\mathrm{PSPACE}$

[1] „ Marked PCP jest rozstrzygalny ” V. Halava, M. Hirvensalo, R. De Wolf (1999)

istnieje więcej niż jeden sposób na „związanie” PCP (być może na wielu!) i wydaje się, że istnieją różnorodne badania nad wieloma wariantami. ograniczenie liczby konkatenowanych bloków lub całkowitej długości konkatenowanych łańcuchów do parametru określonego na wejściu (określonego w formacie binarnym) wydaje się być zakończone NExpSpace, ale nie widzieliśmy tego w piśmie. patrz Ograniczony problem korespondencji pocztowej NP-Complete Proof , tcs.se. jeśli ograniczysz ten sam parametr „długości konkatenacji” do wielomianu wielkości wejściowej, jego pozornie PSpace zostanie ukończone. znowu nie widziałem tego napisanego nigdzie, pomimo pewnych poszukiwań.

istnieją również powiązane badania dotyczące rozwiązywania specjalnych przypadków PCP (nieco przypominające badania Busy Beaver), patrz np. solver PCP Zhao lub [8]. należy zauważyć, że istnieje także niezwykły / pionierski przypadek zastosowania obliczeń DNA do podejścia nieco probabilistycznego [3]. wydaje się również, że Halava [4], [7] prowadzi więcej badań nad innymi rozstrzygającymi wariantami. [5,6] to kolejne różne wyniki.

[1] Problem korespondencji w Tackling Posts autorstwa Zhao (v2?)

[2] Redukcja wielomianu z dowolnego problemu pełnego NP do ograniczonego PCP , cs.se

[3] Wykorzystanie DNA do rozwiązania problemu korespondencji związanej przez Kari i in

[4] O problemie korespondencyjnym dla języków monotonicznych w literach Halava i in

[5] Problem korespondencji pocztowej nad jednoznacznym alfabetem Rudnickiego

[6] Problem korespondencji z częściowo przemiennymi alfabetami Barbara Klunder, Wojciech Rytter

[7] Niektóre nowe wyniki dotyczące problemu korespondencji pocztowej i jego modyfikacji autorstwa Halavy, Harju

[8] Tworzenie trudnych przypadków problemu z korespondencją pocztową autorstwa Lorentza

Ehrenfeucht, Karhumäki i Rozenberg wykazali, że binarne PCP (gdzie domena jest binarna) jest rozstrzygalne. Halava i Holub później wykazali, że tak naprawdę jest w P.