Transformacja pseudowielomianowa

Z Wikipedii

Transformacja pseudowielomianowa – pojęcie wykorzystywane w teorii złożoności obliczeniowej do dowodzenia silnej NP-zupełności problemów decyzyjnych podobnie do zastosowania transformacji wielomianowej przy dowodzeniu NP-zupełności.

Spis treści

1 Definicja formalna
2 Intuicja
3 Zastosowanie
4 Zobacz też

[edytuj] Definicja formalna

Niech π₁ i π₂ będą dwoma problemami decyzyjnymi. Niech $D_{\pi_1}$ i $D_{\pi_2}$ oznaczają ich odpowiednie dziedziny, a $Y_{\pi_1}$ i $Y_{\pi_2}$ podzbiory odpowiednich dziedzin składające się z tych instancji, dla których odpowiedzią jest "TAK". Niech ponadto max(I) oznacza największą liczbę w opisie instancji I, a n(I) rozmiar instancji I.

Transformacją pseudowielomianową problemu π₂ do problemu π₁ nazywa się funkcję

$f: D_{\pi_2} \to D_{\pi_1}$

spełniającą następujące warunki:

Funkcja f przekształca poprawne instancje π₂ na poprawne instancje π₁, tzn.

$\forall I \in D_{\pi_2} : I \in Y_{\pi_2} \iff f(I) \in Y_{\pi_1}$

Funkcja f daje się obliczyć w czasie ograniczonyjm przez wielomian od max(I) i n(I).
Istnieje taki wielomian Q₁, że

$\forall I \in D_{\pi_2} : Q_1(n(f(I))) \geq n(I)$

Istnieje taki wielomian dwóch zmiennych Q₂, że

$\forall I \in D_{\pi_2} : \max(f(I)) \leq Q_2(\max(I), n(I))$

[edytuj] Intuicja

Intuicyjna interpretacja warunków wymienionych w definicji powyżej jest następująca.

Warunek pierwszy to wymaganie, by rozwiązanie, rozumiane tu jako odpowiedź "TAK" lub "NIE", problemu powstałego po transformacji było takie samo jak rozwiązanie problemu transformowanego. Pozwala to na wyciągnięcie wniosków o rozwiązaniu problemu transformowanego na podstawie rozwiązania problemu powstałego po transformacji.

Warunek drugi to ograniczenie na zasoby niezbędne na dokonanie transformacji. Bez tego warunku transformacja ta pozwalałaby przekraczać granice klas złożoności, co pozbawiałoby sensu jej stosowanie w dowodach, że jeden problem należy do tej samej klasy co drugi.

Warunek trzeci zabezpiecza przed wykładniczym skurczeniem rozmiaru instancji problemu. Bez tego warunku transformacja również pozwalałaby przekraczać granice klas złożoności: gdyby transformacja pozwalała na wykładnicze skurczenie rozmiarów instancji problemu, rozwiązanie instancji będącej wynikiem transformacji mogłoby odbyć się w czasie wielomianowym względem rozmiarów początkowej instancji przy użyciu algorytmu działającego wykładniczo względem swojego wejścia (rozmiaru instancji będącej wynikiem transformacji).

Warunek czwarty nie pozwala na wykładniczy wzrost liczb znajdujących się w opisie instancji problemu. Powód istnienia tego warunku w definicji jest analogiczny jak w przypadku warunku trzeciego.

[edytuj] Zastosowanie

Pojęcie transformacji pseudowielomianowej ma zastosowanie w dowodzeniu silnej NP-zupełności problemów decyzyjnych. Dowody takie opierają się na twierdzeniu, zgodnie z którym jeśli problem π₂ jest silnie NP-zupełny i istnieje transformacja pseudowielomianowa problemu π₂ do problemu π₁ oraz $\pi_1 \in NP$ to problem π₁ jest silnie NP-zupełny. Wystarczy więc znaleźć problem silnie NP-zupełny i przetransformowac go pseudowielomianowo do problemu, którego silną NP-zupełność chcemy dowieść.