Transformacja pseudowielomianowa

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.

Definicja formalna

Niech $\pi _{1}$ i $\pi _{2}$ będą problemami decyzyjnymi, $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 $\pi _{2}$ do problemu $\pi _{1}$ nazywa się funkcję

$f\colon D_{\pi _{2}}\to D_{\pi _{1}}$

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

• Funkcja $f$ przekształca poprawne instancje $\pi _{2}$ na poprawne instancje $\pi _{1},$ 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 ograniczonym przez wielomian od $max(I)$ i $n(I).$
• Istnieje taki wielomian $Q_{1},$ że

$\forall I\in D_{\pi _{2}}:Q_{1}(n(f(I)))\geqslant n(I).$

• Istnieje taki wielomian dwóch zmiennych $Q_{2},$ że

$\forall I\in D_{\pi _{2}}:\max(f(I))\leqslant Q_{2}(\max(I),n(I)).$

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 gwarantuje, że podproblem $\pi _{1/P_{1}}$ świadczący o silnej NP-zupełności $\pi _{1}$ zostanie przekształcony przez $f$ do pewnego podproblemu $\pi _{2/P_{2}},$ gdzie $P_{1}$ i $P_{2}$ są wielomianami.

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 $\pi _{2}$ jest silnie NP-zupełny i istnieje transformacja pseudowielomianowa problemu $\pi _{2}$ do problemu $\pi _{1}$ oraz $\pi _{1}\in NP$ to problem $\pi _{1}$ jest silnie NP-zupełny. Wystarczy więc znaleźć problem silnie NP-zupełny i przetransformować go pseudowielomianowo do problemu, którego silną NP-zupełność chcemy dowieść.

Zobacz też

• problem silnie NP zupełny