Transformacja pseudowielomianowa: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
wytłumaczenie warunku czwartego zgodnie z użyciem w dowodzie |
m drobne redakcyjne |
||
Linia 2:
== Definicja formalna ==
Niech <math>\pi_1</math> i <math>\pi_2</math> będą problemami decyzyjnymi, <math>D_{\pi_1}</math> i <math>D_{\pi_2}</math> oznaczają ich odpowiednie dziedziny, a <math>Y_{\pi_1}</math> i <math>Y_{\pi_2}</math> podzbiory odpowiednich dziedzin składające się z tych instancji, dla których odpowiedzią jest "TAK". Niech ponadto <math>max(I)</math> oznacza największą liczbę w opisie instancji <math>I</math>, a <math>n(I)</math> rozmiar instancji <math>I</math>.▼
▲Niech <math>D_{\pi_1}</math> i <math>D_{\pi_2}</math> oznaczają ich odpowiednie dziedziny, a <math>Y_{\pi_1}</math> i <math>Y_{\pi_2}</math> podzbiory odpowiednich dziedzin składające się z tych instancji, dla których odpowiedzią jest "TAK". Niech ponadto max(I) oznacza największą liczbę w opisie instancji I, a n(I) rozmiar instancji I.
'''Transformacją pseudowielomianową''' problemu <math>\pi_2</math> do problemu <math>\pi_1</math> nazywa się funkcję
: <math>f: D_{\pi_2} \to D_{\pi_1}</math>
spełniającą następujące warunki:
* Funkcja <math>f</math> przekształca poprawne instancje
: <math>\forall I \in D_{\pi_2} : I \in Y_{\pi_2} \iff f(I) \in Y_{\pi_1}</math>
* Funkcja <math>f</math> daje się obliczyć w czasie
* Istnieje taki
: <math>\forall I \in D_{\pi_2} : Q_1(n(f(I))) \geqslant n(I)</math>
* Istnieje taki
: <math>\forall I \in D_{\pi_2} : \max(f(I)) \leqslant Q_2(\max(I), n(I))</math>
Linia 28 ⟶ 27:
== Zastosowanie ==
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
== Zobacz też ==
| |||