Redukcja wielomianu z dowolnego problemu NP-zupełnego do ograniczonego PCP

Podręczniki wszędzie założyć, że Bounded post Korespondencja Problem jest NP-zupełny (nie więcej niż $N$ indeksy dozwolony z powtórzeń). Nigdzie jednak nie pokazano prostej (jak w czymś, co student może zrozumieć) wielomianowej redukcji czasu z innego problemu pełnego NP.

Jednak każda redukcja, o której mogę myśleć, ma charakter wykładniczy (według $N$ lub wielkości serii) w czasie wykonywania. Być może można wykazać, że można go zredukować do SAT?

Jak to często bywa w przypadku redukcji NP, warto szukać podobnych problemów. W szczególności trudno jest zakodować globalne warunki, takie jak „widziałem niektóre węzły” w PCP (z wielomianowo wieloma kafelkami), co przeciwwskazuje problemy z grafem, problemy z pakowaniem wymagałyby od nas zakodowania liczb jednoznacznych w PCP (tworząc wykładniczo dużą instancję), i wkrótce. Dlatego można się spodziewać, że problem ciągu z tylko lokalnymi ograniczeniami będzie działać najlepiej.

Rozważ wersję decyzyjną najkrótszego wspólnego problemu nadsekwencji :

Biorąc pod uwagę dwa ciągi z | a | = n i | b | = M oraz k ∈ N , zdecydować, czy istnieje ciąg c ∈ Ď + z | c | ≤ k , tak że i b są subsekwencje C .$a,b \in \Sigma^+$$|a|=n$$|b|=m$$k \in \mathbb{N}$$c \in \Sigma^+$$|c| \leq k$$a$$b$$c$

Chodzi o to, aby pozwolić PCP kompilacji supersequences z i B od lewej do prawej, kodujący w pokrywania płytkami w jakiej pozycji jesteśmy w i B , odpowiednio. Użyje jednego kafelka na symbol w$a$$b$$a$$b$kafelka c , więc k odpowiada granicy BPCP: jeśli możemy rozwiązać ten PCP za pomocą k płytek ≤ k , możesz odczytać powszechną supersekwencję o równej długości i odwrotnie.$c$$k$$\leq k$

Konstrukcja kafelków jest nieco nużąca, ale dość wyraźna. Pamiętaj, że nie będziemy tworzyć kafelków, które nie przekazują lub b ; takie nigdy nie mogą być częścią najkrótszej wspólnej nadrzędności, więc są zbędne. Można je łatwo dodać bez naruszenia właściwości redukcji.$a$$b$

Liczby na zakładkach są kodowane binarnie, ale za pomocą symboli spoza i dopełniania ich do wspólnej długości log $\Sigma$ . W ten sposób upewniamy się, że kafelki są używane zgodnie z grafiką (tetris), to znaczy znaki i nakładające się na siebie indeksy nie mieszają się (PCP samo w sobie tego nie zapobiega). Potrzebujemy:$\log \max(m,n)$

• Płytki początkowe : może zaczynać się od 1 , b 1 lub obu, jeśli są równe.$c$$a_1$$b_1$
• Płytki pośrednie: może przejść do następnego symbolu z litery a , b lub obu, jeśli są równe.$c$$a$$b$
• Kafelki kończące : kończy się na ostatnim symbolu a (jeśli już widział się ostatni z b ), podobnie dla b , lub na ostatnim symbolu obu.$c$$a$$b$$b$

To są schematy kafelków. Zauważ, że płytki pośrednie muszą być tworzone dla wszystkich par . Jak wspomniano powyżej, utwórz kafelki bez ∗ tylko wtedy, gdy odpowiednie postacie w$(i,j) \in [n]\times [m]$$*$ i b meczu.$a$$b$

^{[ źródło ]}

Są symboliczne dla „nie obchodzi”; w rzeczywistych kafelkach drugi symbol będzie musiał zostać skopiowany. Zauważ, że liczba płytek jest w Θ ( m n ), a każda płytka ma długość 4 log max ( m , n ) + 1 , więc zbudowana instancja BPCP (ponad alfabetem Σ ∪ { 0 , 1 $*$$\Theta(mn)$$4\log \max(m,n) + 1$$\Sigma \cup \{0,1\}$plus symbole separacji) ma wielkość wielomianową. Ponadto konstrukcja każdej płytki jest wyraźnie możliwa w czasie wielomianowym. Dlatego proponowana redukcja jest rzeczywiście prawidłową transformacją wielomianową, która redukuje najczęstszy NP najkrótszy wspólny problem nadsekwencji do BPCP.

Myślę, że możesz udowodnić, że BPCP jest kompletny NP, stosując redukcję podobną do tej zastosowanej w celu udowodnienia jego nierozstrzygalności. Udowodnimy bezpośrednio, że BPCP jest kompletny z NP, pokazując, jak zredukować do niego dowolny problem w NP w czasie wielomianowym.

Standardowa redukcja zastosowana w celu udowodnienia, że ​​PCP jest nierozstrzygalna ( naszkicowana tutaj ) działa poprzez zbudowanie serii płytek tak, że istnieje rozwiązanie PCP, jeśli istnieje akceptowalne obliczenie danej TM na łańcuchu w . Liczba kafelków utworzonych w tej redukcji jest wielomianowo duża - konkretnie liczba skonstruowanych domino jest pewną funkcją wielkości alfabetu taśmy i liczby stanów w TM. Jedynym domino, którego rozmiar może być duży, jest początkowe domino, które ma $M$$w$$w$napisane na nim. Jeśli uogólnimy tę redukcję z pracy na deterministycznych bazach TM na pracę na niedeterministycznych bazach TM, wówczas wprowadzi to co najwyżej pewną stałą liczbę domino, ponieważ liczba przejść jest skończona. W związku z tym możemy skonstruować standardowy zestaw domino dla normalnego zmniejszenia nierozstrzygalności w czasie wielomianowym.

Biorąc to pod uwagę, możemy zredukować dowolny problem NP do BPCP w następujący sposób - biorąc pod uwagę każdy problem NP, ma on pewien NTM w czasie wielomianowym, który działa w czasie p ( n ) . Następnie możemy zredukować ten problem do BPCP w czasie wielomianowym w następujący sposób - skonstruuj standardowy zestaw domino z M , a następnie zapytaj, czy istnieje rozwiązanie wykorzystujące domino f ( p ( n ) ) , gdzie f jest jakąś funkcją wielomianową wyrażającą liczba domino niezbędnych do istnienia rozwiązania (prawdopodobnie jest to coś w rodzaju n $M$$p(n)$$M$$f(p(n))$$f$$n^2$i na pewno nie jest wykładniczy). Następnie, używając tego samego dowodu, którego używasz do wykazania, że ​​PCP jest nierozstrzygalny, możesz udowodnić, że istnieje rozwiązanie dla tej instancji BPCP, która używa co najwyżej kafelków jeśli oryginalny NTM M akceptuje mw obrębie p ( n ) kroki. W rezultacie mamy redukcję czasu wielomianowego z każdego problemu w NP do BPCP, więc BPCP jest trudny do NP.$f(p(n))$$M$$m$$p(n)$

(Powinniśmy również pokazać, że BPCP jest w NP, ale to proste; po prostu niedeterministycznie zgadnij, które domina należy uporządkować, a następnie sprawdź to deterministycznie).

Mam nadzieję że to pomoże!