Redukcja wielomianu
Wielomian redukcja jest narzędziem do informatyki teoretycznej , a dokładniej do teorii złożoności . Jest to szczególna klasa redukcji, która jest szczególnie ważna, w szczególności dla problemu P = NP .
Definicja
W ramach języków formalnych dla problemów decyzyjnych mówimy, że język jest redukowalny w czasie wielomianowym do języka (oznaczonego ), jeśli istnieje obliczalna funkcja w czasie wielomianowym taka, że dla wszystkich , wtedy i tylko wtedy, gdy . Wywołujemy funkcję w funkcję redukcji oraz wielomian algorytmu, który oblicza nazywa algorytm redukcji .
L1{\ displaystyle L_ {1} \!}
L2{\ displaystyle L_ {2} \!}
L1≤P.L2{\ displaystyle L_ {1} \ leq _ {P} L_ {2}}
fa:{0,1}∗→{0,1}∗{\ Displaystyle f: \ lewo \ {0,1 \ prawo \} ^ {*} \ rightarrow \ lewo \ {0,1 \ prawo \} ^ {*}}
x∈{0,1}∗{\ Displaystyle x \ in \ lewo \ {0,1 \ prawo \} ^ {*}}
x∈L1{\ displaystyle x \ in L_ {1}}
fa(x)∈L2{\ displaystyle f (x) \ in L_ {2}}
fa{\ displaystyle f \!}
fa{\ displaystyle f \!}![f \!](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8e5892a78a5fde92fb689f3fe6721034bac8d40)
Związek między problemem decyzyjnym a związanym z nim językiem
Kodowanie
Albo problem decyzyjny . Instancje tego problemu są obiektami abstrakcyjnymi w tym sensie, że ich definicja jest czysto matematyczna. Jednak aby umożliwić realizację tego problemu, muszą one być przedstawione w formie zrozumiałej dla programu. Tu pojawia się pojęcie kodowania . Definiujemy funkcję kodowania problemu decyzyjnego jako aplikację iniekcyjną, która kojarzy się z zestawem abstrakcyjnych instancji elementu . Zatem, gdy programista koduje problem, zmienne reprezentujące wystąpienia problemu są tłumaczone (przez kompilator w przypadku języków statycznych, przez interpretera w przypadku języków dynamicznych) na język binarny. Kodowanie jest zatem sposobem na przejście od abstrakcyjnego problemu do konkretnego problemu. W rzeczywistości, jeśli rozwiązaniem problemu decyzyjnego jest instancja abstrakcyjna, gdy rozwiązanie konkretnego problemu jest rozwiązaniem Instancji . Jest jednak mały problem: możliwe jest, że elementy nie odpowiadają żadnemu wystąpieniu problemu (to znaczy nie mają poprzednika ). Dla wygody zakłada się, że każdy taki łańcuch to obraz 0.
Q{\ displaystyle Q \!}
vs{\ displaystyle c \!}
Q{\ displaystyle Q \!}
Q{\ displaystyle Q \!}
{0,1}∗{\ Displaystyle \ lewo \ {0,1 \ prawo \} ^ {*}}
ja∈ja{\ displaystyle ja \ in I}
Q(ja)∈{0,1}{\ Displaystyle Q (i) \ in \ lewo \ {0,1 \ prawo \}}
vs(ja)∈{0,1}∗{\ Displaystyle c (i) \ in \ lewo \ {0,1 \ prawo \} ^ {*}}
Q(ja){\ Displaystyle Q (i) \!}
{0,1}∗{\ Displaystyle \ lewo \ {0,1 \ prawo \} ^ {*}}![\ left \ {0,1 \ right \} ^ *](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6bba5bf1e997c3246053f563e8eea4e41a36ccd)
Związek między problemami decyzyjnymi a algorytmami je rozwiązującymi
- Algorytm akceptuje ciąg znaków, jeśli przy danych wejściowych algorytm kończy działanieW{\ Displaystyle A \!}
x∈{0,1}∗{\ Displaystyle x \ in \ lewo \ {0,1 \ prawo \} ^ {*}}
x{\ displaystyle x \!}
W(x)=1{\ Displaystyle A (x) = 1 \!}
- Algorytm odrzuca ciąg, jeśli .W{\ Displaystyle A \!}
x{\ displaystyle x \!}
W(x)=0{\ Displaystyle A (x) = 0 \!}![A (x) = 0 \!](https://wikimedia.org/api/rest_v1/media/math/render/svg/2604870738d4dde1faa444a0a65cf898dd5fdb5d)
Zaakceptowano język
- To znaczy, język akceptowany przez algorytm to zbiór ciągów znaków akceptowany przez algorytm .W{\ Displaystyle A \!}
L={x∈{0,1}∗:W(x)=1}{\ Displaystyle L = \ lewo \ {x \ in \ lewo \ {0,1 \ prawo \} ^ {*}: A (x) = 1 \ prawo \}}![L = \ lewo \ {x \ in \ lewo \ {0, 1 \ prawo \} ^ *: A (x) = 1 \ prawo \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f19059b5bc803d678354b0b3577c7fbb85e61c04)
Język zdecydowany
- Język jest wybierany przez algorytm, jeśli jakikolwiek ciąg bitów nienależący do zostanie odrzucony przez .L{\ Displaystyle L \!}
W{\ Displaystyle A \!}
L{\ Displaystyle L \!}
W{\ Displaystyle A \!}![W\!](https://wikimedia.org/api/rest_v1/media/math/render/svg/712fdf8c6a6ba7341d0cdfd7a2e039f0b5371ed2)
Klasa i język złożoności
Możemy nieformalnie zdefiniować klasę złożoności jako zbiór języków, których przynależność jest określona przez miarę złożoności algorytmu, który określa, czy dany ciąg należy do języka . Zatem klasę złożoności można zdefiniować jako zbiór języków, o których decyduje wielomianowy algorytm czasu.
x{\ displaystyle x \!}
L{\ Displaystyle L \!}
P.{\ Displaystyle P \!}
{0,1}∗{\ Displaystyle \ lewo \ {0,1 \ prawo \} ^ {*}}![\ left \ {0,1 \ right \} ^ *](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6bba5bf1e997c3246053f563e8eea4e41a36ccd)
Użyteczność
Pojęcie redukcji czasu wielomianu jest wykorzystywane w ramach teorii złożoności algorytmów, aby umożliwić klasyfikację problemów. W istocie pozwala wykazać w sposób formalny iw czasie wielomianowym, że problem jest co najmniej tak samo trudny jak inny: jeśli wtedy nie jest trudniejszy niż , lub powiedziany w bardziej teoretyczny sposób: i mają tę samą klasę. złożoności.
L1≤P.L2{\ displaystyle L_ {1} \ leq _ {P} L_ {2}}
L1{\ displaystyle L_ {1} \!}
L2{\ displaystyle L_ {2} \!}
L1{\ displaystyle L_ {1} \!}
L2{\ displaystyle L_ {2} \!}![L_2 \!](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4bdbc2923a7434b1346a920df72de670e27cb64)
Przykłady redukcji
- Pokryty do sumy podzbioru
- Kliknij, aby przejść do 3-SAT
- SAT do 3-SAT
- Suma podzbioru do SAT
- 3-SAT, aby kliknąć
- 3-SAT do osłony wierzchołków
Uwagi i odniesienia
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">