Czy problem korespondencyjny występuje w NP?

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 ,

$$(t_1/b_1, t_2/b_2,...t_n/b_n)$$ $t_1, t_2,...,t_n$$t$ 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.$b_1, b_2, ..., b_n$$b$$t$$b$

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!

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.