Transformacja pseudowielomianowa: Różnice pomiędzy wersjami

[wersja nieprzejrzana][wersja nieprzejrzana]
Usunięta treść Dodana treść
mNie podano opisu zmian
Linia 28:
 
== Zastosowanie ==
Pojęcie '''transformacji pseudowielomianowej''' ma zastosowanie w dowodzeniu [[Problem silnie NP zupełny|silnej NP-zupełności]] [[Problem decyzyjny|problemów decyzyjnych]]. Dowody takie opierają się na twierdzeniu, zgodnie z którym jeśli problem &pi;<sub>2</sub> jest [[Problem silnie NP zupełny|silnie NP-zupełny]] i istnieje '''transformacja pseudowielomianowa''' problemu &pi;<sub>2</sub> do problemu &pi;<sub>1</sub> oraz <math>\pi_1 \in NP</math> to problem &pi;<sub>1</sub> 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 przetransformowac go pseudowielomianowo do problemu, którego [[Problem silnie NP zupełny|silną NP-zupełność]] chcemy dowieść.
 
== Zobacz również ==