Transformacja pseudowielomianowa

W teorii złożoności obliczeniowej transformacja pseudowielomianowa jest funkcją, która odwzorowuje wystąpienia jednego problemu silnie NP-zupełnego na inny i jest obliczalna w czasie pseudowielomianowym .

Definicje

Maksymalny parametr liczbowy

Niektóre problemy obliczeniowe są parametryzowane liczbami, których wielkość wykładniczo przekracza rozmiar danych wejściowych. Na przykład problem sprawdzenia, czy liczba n jest liczbą pierwszą , można rozwiązać naiwnie sprawdzając czynniki kandydujące w $}$${\ displaystyle {\ sqrt {n$ podziałów, a zatem wykładniczo więcej niż rozmiar wejściowy. ${\ Displaystyle O (\ log (n))}$ . Przypuszczam, że $L}$ kodowaniem problemu obliczeniowego w alfabecie $,$ a następnie ${\$

${\ Displaystyle \ nazwa operatora {Num} _ {\ Pi}: \ Sigma ^ {*} \ do \ mathbb {N}}$

$,$ funkcją $.$ wystąpienia problemu $_$ _ do $liczbowego$ parametru .

Transformacja pseudowielomianowa

$Załóżmy$$\$ że i $}}$ decyzyjnymi i $L_$${1}$ są ich kodowaniem w odpowiednio ${\ displaystyle \ Sigma _ {1}}$ i ${\ displaystyle \ Sigma _ {2}}$ .

Transformacja pseudowielomianowa z jest funkcją $Sigma$$displaystyle f$${$ tak, że

1. ${\ Displaystyle \ forall w \ in \ Sigma _ {1} \ quad w \ in L_ {1} \iff f (w) \ w L_ { 2}}$
2. ${\ Displaystyle \ forall w \ in \ Sigma _ {1} \ quad f (w)}$ można obliczyć w wielomianie czasu w dwóch zmiennych ${\ displaystyle \ nazwa operatora {Num} _{\Pi _{1}}(w)}$ i ${\ displaystyle | w |}$
3. ${\ Displaystyle \ istnieje Q_ {A} \ in \ mathbb {N} [X] \ quad \ forall w \ in \ Sigma _ {1} \ quad | w | \ równoważnik Q_{A}(|f(w)|)}$
4. ${\ Displaystyle \ istnieje Q_ {B} \ in \ mathbb {N} [X, Y] \ quad \ forall w \ in \ Sigma _ {1} \ quad \ nazwa operatora {Num} _ {\ Pi _ {2}} (f(w))\leq Q_{B}(\nazwa operatora {Num} _{\Pi _{1}}(w),|w|)}$

$Pi _ {1}}$ pozwala rozumować o przypadkach ( i odwrotnie), (2) zapewnia ${\ displaystyle \$ że podjęcie decyzji $za$ transformacji $.$ pseudo-wielomianu decydującego o tym, że jest pseudowielomianem, (3) wymusza $​​rośnie$ wystarczająco szybko, aby ${\ displaystyle L_ {2}}$ musi mieć rozstrzygający pseudowielomian i (4) wymusza, aby podproblem problemu, który świadczy o jego silnej ${\ displaystyle L_ {1}} podproblem jest sam w sobie$ -kompletności (tj. wszystkie instancje mają parametry numeryczne ograniczone wielomianem w rozmiarze wejściowym i L $odwzorowywany$ na podproblem, którego instancje mają parametry numeryczne ograniczone wielomianem w rozmiarze wejściowym.

Udowodnienie silnej NP-kompletności

Poniższy lemat pozwala wyprowadzić silną NP-zupełność z istnienia transformacji:

Jeśli jest to problem decyzyjny silnie NP-zupełny, $jest to problem decyzyjny w NP i$${\ displaystyle \ Pi _ {1}$ transformacja pseudowielomianowa z $Displaystyle \ Pi _ {1}}$$\ Pi _ {2}}$ Π $\ Displaystyle$ , to jest silnie NP-zupełny

Dowód lematu

Załóżmy, że $Pi _$ to problem decyzyjny silnie NP-zupełny, zakodowany przez $jest$$\$ Π ${1}$ { problemem decyzyjnym $_$$zakodowanym$ _

Niech będzie transformacją pseudowielomianową z $} do fa : L 1 → L 2 {$${\ displaystyle \ Pi _ {1}$$do$ L_ $}$ Pi $_$$.$ z w

${\ Displaystyle L_ {1/P} = \ {w \ w L_ {1}: \ nazwa operatora {Num} _ {\ Pi _ {1}} (w) \ równoważnik P(|w|)\}}$ definicji silnej NP $P$ , jest NP-zupełny.

Dla ${\ Displaystyle {\ widehat {P}} (n) = Q_ {B} (P (Q_ {A} (n)), Q_ {A} (n))}$ i dowolny jest ${\ displaystyle w \ w L_ {1/P}}$

${\ Displaystyle {\ rozpocząć {wyrównane} \ operatorname {Num} _ {\ Pi _ {2}} (f (w)) i \ równoważnik Q_ {B} (\ operatorname {Num} _ {\ Pi _ {1} }(w),|w|)&&{\text{(definicja }}f{\text{)}}\\[4pt]&\leq Q_{B}(P(w),|w|)&& {\text{(własność }}L_{1/P}{\text{)}}\\[4pt]&\leq Q_{B}(P(Q_{A}(|f(w)|)) ,Q_{A}(|f(w)|))&&{\text{(definicja }}f{\text{)}}\\[4pt]&\leq {\widehat {P}}(|f (w)|)&&{\text{(definicja }}{\widehat {P}}{\text{)}}\end{aligned}}}$

Dlatego,

${\ Displaystyle f (L_ {1/P}) = \ {w\in L_{2}:\operatorname {Num} _{\Pi _{2}}(w)\leq {\widehat {P}}(|w|)\}=L_{2/{\widehat {P}}}}$

Ponieważ $}}$$_$ - $jest$ można obliczyć w czasie wielomianowym, zupełny.

Z tego oraz z definicji silnej NP-zupełności wynika, że $​​jest ona$ NP-zupełna