Transformacja pseudowielomianowa: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m drobne techniczne, WP:SK |
wytłumaczenie warunku czwartego zgodnie z użyciem w dowodzie |
||
Linia 25:
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 <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.
== Zastosowanie ==
| |||