Transformacja pseudowielomianowa: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m →Intuicja: lit. |
m BrokenglaSSbot poprawia LaTeX |
||
Linia 3:
== Definicja formalna ==
Niech π<sub>1</sub> i π<sub>2</sub> będą dwoma problemami decyzyjnymi.
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 π<sub>2</sub> do problemu π<sub>1</sub> nazywa się funkcję
Linia 10:
* 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]] Q<sub>1</sub>, że
:<math>\forall I \in D_{\pi_2} : Q_1(n(f(I))) \geq n(I)</math>
* Istnieje taki [[wielomian]] dwóch zmiennych Q<sub>2</sub>, że
:<math>\forall I \in D_{\pi_2} : \max(f(I)) \leq Q_2(\max(I), n(I))</math>
== Intuicja ==
| |||