Wikipedia

Transformacja pseudowielomianowa: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
m drobne redakcyjne
Linia 1:
'''Transformacja pseudowielomianowa''' to– pojęcie wykorzystywane w [[Teoriateoria złożoności obliczeniowej|teorii złożoności obliczeniowej]] do dowodzenia [[Problemproblem silnie NP zupełny|silnej NP-zupełności]] [[Problemproblem decyzyjny (teoria obliczeń)|problemów decyzyjnych]] podobnie do zastosowania [[Transformacjatransformacja wielomianowa|transformacji wielomianowej]] przy dowodzeniu [[Problemproblem NP zupełny|NP-zupełności]].
 
== Definicja formalna ==
Linia 30:
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 &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żteż ==
* [[Problemproblem silnie NP zupełny]]
 
[[Kategoria:Teoria obliczeń]]
Źródło: „https://pl.wikipedia.org/wiki/Transformacja_pseudowielomianowa”