Transformacja pseudowielomianowa

Transformacja Pseudowielomianowa

Transformacja pseudowielomianowa to pojęcie w teorii złożoności obliczeniowej, używane do dowodzenia silnej NP-zupełności problemów decyzyjnych.

Definicja Formalna

Niech $pi\_1$ i $pi\_2$ będą problemami decyzyjnymi, a $D\_\{pi\_1\}$ i $D\_\{pi\_2\}$ ich dziedzinami. Zbiór $Y\_\{pi\_1\}$ i $Y\_\{pi\_2\}$ oznacza instancje, dla których odpowiedzią jest „TAK”.

Transformacją pseudowielomianową problemu $pi\_2$ do problemu $pi\_1$ jest funkcja $fcolon\; D\_\{pi\_2\}\; to\; D\_\{pi\_1\}$, która spełnia 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$ jest obliczalna w czasie ograniczonym przez wielomian od $max(I)$ i $n(I)$.
• Istnieje wielomian $Q\_1$, taki że $forall\; I\; in\; D\_\{pi\_2\}\; :\; Q\_1(n(f(I)))\; geqslant\; n(I)$.
• Istnieje wielomian $Q\_2$, taki że $forall\; I\; in\; D\_\{pi\_2\}\; :\; max(f(I))\; leqslant\; Q\_2(max(I),\; n(I))$.

Intuicja

Warunki definicji mają następujące znaczenie:

• Pierwszy warunek zapewnia, że odpowiedzi na problemy są zgodne po transformacji.
• Drugi warunek ogranicza zasoby potrzebne do dokonania transformacji, co jest kluczowe dla zachowania klas złożoności.
• Trzeci warunek chroni przed wykładniczym skurczeniem instancji, co mogłoby fałszywie sugerować przynależność do innej klasy złożoności.
• Czwarty warunek gwarantuje, że przekształcenie zachowuje silną NP-zupełność.

Zastosowanie

Transformacje pseudowielomianowe są używane w dowodzeniu silnej NP-zupełności problemów decyzyjnych. Jeśli problem $pi\_2$ jest silnie NP-zupełny i istnieje transformacja pseudowielomianowa do problemu $pi\_1$, który należy do klasy NP, to $pi\_1$ również jest silnie NP-zupełny. Proces ten polega na znalezieniu problemu silnie NP-zupełnego i przekształceniu go pseudowielomianowo do problemu, którego silną NP-zupełność chcemy dowieść.