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
