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
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.
complexity-theory
decision-problem
np
phhoang
źródło
źródło
Odpowiedzi:
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!
źródło
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.
źródło