Transformacja pseudowielomianowa: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m drobne redakcyjne |
m drobne techniczne, WP:SK |
||
Linia 2:
== Definicja formalna ==
Niech
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>f: D_{\pi_2} \to D_{\pi_1}</math>
spełniającą następujące warunki:
* Funkcja f przekształca poprawne instancje π<sub>2</sub> na poprawne instancje π<sub>1</sub>, tzn.
: <math>\forall I \in D_{\pi_2} : I \in Y_{\pi_2} \iff f(I) \in Y_{\pi_1}</math>
* Funkcja f daje się obliczyć w czasie ograniczonyjm przez [[wielomian]] od max(I) i n(I).
* Istnieje taki [[wielomian]]
: <math>\forall I \in D_{\pi_2} : Q_1(n(f(I))) \
* Istnieje taki [[wielomian]] dwóch zmiennych
: <math>\forall I \in D_{\pi_2} : \max(f(I)) \
== Intuicja ==
| |||