Czy problem korespondencyjny występuje w NP?

12

Właśnie przeczytałem kilka stron w książce Sipsera Wprowadzenie do teorii obliczeń na temat problemu z korespondencją pocztową i myślę, że PCP jest w rzeczywistości w NP. Certyfikującej wynosi: dla konfiguracji wejściowej stos łączenie T 1 , T 2 , . . . , t n jako ciąg t i konkatenacja b 1 , b

(t1/b1,t2/b2,...tn/bn)
t1,t2,...,tnt Jako łańcuch B , a następnie porównanie T i B w celu sprawdzenia, czy oba są równe, a następnie wnioskować, czy sygnał wejściowy jest rzeczywiście rozwiązanie PCP.b1,b2,...,bnbtb
phhoang
źródło
2
a / ograniczona wersja / wariant tego problemu jest NP kompletny. patrz np. ograniczony PCP NP complete / Theoretical Computer Science
vzn

Odpowiedzi:

19

Korespondencja Problem Post nierozstrzygalny, aw szczególności jest to nie w NP. Powodem, dla którego twój pomysł nie działa, jest to, że świadek niekoniecznie musi być wielomianowy (w rzeczywistości właśnie to udowodniłeś). Oznacza to, że aby Twój certyfikat mógł udowodnić, że problem z korespondencją pocztową występuje w NP, musi on działać w czasie wielomianowym (pod względem wielkości instancji PCP ). Okazuje się, że w tym przypadku nie zawsze istnieje rozwiązanie wielomianowe, nawet jeśli problem można rozwiązać. W rzeczywistości nie ma możliwości obliczenia wielkości potencjalnego rozwiązania, ponieważ w przeciwnym razie problem byłby rozstrzygalny!

Yuval Filmus
źródło
11

Twój świadek jest wielomianem pod względem wielkości rozwiązania, a nie wielkości danych wejściowych. Nie masz możliwości ograniczenia długości potencjalnych rozwiązań. Twój dowód pokazuje, że PCP można wyliczyć rekurencyjnie.

phs
źródło