Transformacja pseudowielomianowa

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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[edytuj | edytuj kod]

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

Intuicja[edytuj | edytuj kod]

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.

Zastosowanie[edytuj | edytuj kod]

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 | edytuj kod]