Transformacja pseudowielomianowa: Różnice pomiędzy wersjami

'''Transformacja pseudowielomianowa''' – pojęcie wykorzystywane w [[teoriaZłożoność złożoności obliczeniowejobliczeniowa|teorii złożoności obliczeniowej]] do dowodzenia [[problemProblem silnie NP -zupełny|silnej NP-zupełności]] [[problem decyzyjny (teoria obliczeń)|problemów decyzyjnych]] podobnie do zastosowania [[transformacja wielomianowa|transformacji wielomianowej]] przy dowodzeniu [[problemProblem NP -zupełny|NP-zupełności]].

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

: <math>f:\colon D_{\pi_2} \to D_{\pi_1}</math>

* Funkcja <math>f</math> przekształca poprawne instancje <math>\pi_2</math> na poprawne instancje <math>\pi_1,</math>, tzn.

: <math>\forall I \in D_{\pi_2} : I \in Y_{\pi_2} \iff f(I) \in Y_{\pi_1}.</math>

* Funkcja <math>f</math> daje się obliczyć w czasie ograniczonym przez [[wielomian]] od <math>max(I)</math> i <math>n(I).</math>.

* Istnieje taki wielomian <math>Q_1,</math>, że

: <math>\forall I \in D_{\pi_2} : Q_1(n(f(I))) \geqslant n(I).</math>

* Istnieje taki wielomian dwóch zmiennych <math>Q_2,</math>, że

: <math>\forall I \in D_{\pi_2} : \max(f(I)) \leqslant Q_2(\max(I), n(I)).</math>

Warunek pierwszy to wymaganie, by rozwiązanie, rozumiane tu jako odpowiedź "TAK"„TAK” lub "NIE"„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 czwarty gwarantuje, że podproblem <math>\pi_{1/P_1}</math> świadczący o silnej NP-zupełności <math>\pi_1</math> zostanie przekształcony przez <math>f</math> do pewnego podproblemu <math>\pi_{2/P_2},</math>, gdzie <math>P_1</math> i <math>P_2</math> są  wielomianami.

Pojęcie '''transformacji pseudowielomianowej''' ma zastosowanie w dowodzeniu [[Problem silnie NP -zupełny|silnej NP-zupełności]] problemów decyzyjnych. Dowody takie opierają się na twierdzeniu, zgodnie z którym jeśli problem <math>\pi_2</math> jest [[Problem silnie NP -zupełny|silnie NP-zupełny]] i istnieje '''transformacja pseudowielomianowa''' problemu <math>\pi_2</math> do problemu <math>\pi_1</math> oraz <math>\pi_1 \in NP</math> to problem <math>\pi_1</math> jest [[Problem silnie NP zupełny|silnie NP-zupełny]]. Wystarczy więc znaleźć problem [[Problem silnie NP zupełny|silnie NP-zupełny]] i przetransformować go pseudowielomianowo do problemu, którego [[Problem silnie NP -zupełny|silną NP-zupełność]] chcemy dowieść.

* [[Problem silnie NP-zupełny|problem silnie NP zupełny]]