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 formalnaEdytuj

Niech   i   będą problemami decyzyjnymi,   i   oznaczają ich odpowiednie dziedziny, a   i   podzbiory odpowiednich dziedzin składające się z tych instancji, dla których odpowiedzią jest „TAK”. Niech ponadto   oznacza największą liczbę w opisie instancji   a   rozmiar instancji  

Transformacją pseudowielomianową problemu   do problemu   nazywa się funkcję

 

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

  • Funkcja   przekształca poprawne instancje   na poprawne instancje   tzn.
 
  • Funkcja   daje się obliczyć w czasie ograniczonym przez wielomian od   i  
  • Istnieje taki wielomian   że
 
  • Istnieje taki wielomian dwóch zmiennych   że
 

IntuicjaEdytuj

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   świadczący o silnej NP-zupełności   zostanie przekształcony przez   do pewnego podproblemu   gdzie   i   są wielomianami.

ZastosowanieEdytuj

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   to problem   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żEdytuj