Polinom redukció
A polinom redukció az elméleti számítástechnika , pontosabban a komplexitáselmélet eszköze . A redukciók egy speciális osztálya különösen fontos, különösen a P = NP probléma szempontjából .
Meghatározás
Ennek keretében a hivatalos nyelv a döntési problémák , azt mondjuk, hogy egy nyelv van redukálható polinomiális időben , hogy egy nyelvet (jele ), ha létezik egy kiszámítható függvény polinom időben úgy, hogy minden , akkor és csak akkor . Felhívjuk a funkció a csökkentést , és egy polinomiális algoritmust, amely kiszámítja az úgynevezett redukciós algoritmus .
L1{\ displaystyle L_ {1} \!}L2{\ displaystyle L_ {2} \!}L1≤PL2{\ displaystyle L_ {1} \ leq _ {P} L_ {2}} f:{0,1}∗→{0,1}∗{\ displaystyle f: \ left \ {0,1 \ right \} ^ {*} \ rightarrow \ left \ {0,1 \ right \} ^ {*}}x∈{0,1}∗{\ displaystyle x \ in \ bal \ {0,1 \ jobb \} ^ {*}}x∈L1{\ displaystyle x \ in L_ {1}}f(x)∈L2{\ displaystyle f (x) \ in L_ {2}}f{\ displaystyle f \!}f{\ displaystyle f \!}
Kapcsolat a döntési probléma és a hozzá tartozó nyelv között
Kódolás
Vagy egy döntési probléma . Ennek a problémának az előfordulásai absztrakt objektumok abban az értelemben, hogy definíciójuk tisztán matematikai. A probléma megoldásának lehetővé tételéhez azonban a program számára érthető formában kell őket képviselni. Itt jön a kódolás fogalma . A döntési probléma kódolási funkcióját úgy definiáljuk, mint egy injektív alkalmazást, amely társul a (z) . Így amikor egy programozó problémát kódol, a probléma példányait reprezentáló változókat bináris nyelvre fordítják ( statikus nyelvek esetén a fordító , dinamikus nyelvek esetén pedig az tolmács ) bináris nyelvre. A kódolás tehát az elvont problémáról a konkrét problémára való áttérés módja. Sőt, ha a megoldást a döntési probléma elméleti például az , ha a Bíróság megoldás konkrét probléma van . Van azonban egy kis probléma, hogy lehetnek olyan elemei, amelyek nem felelnek meg a probléma egyetlen példájának sem (vagyis hogy nincs előzményük ). A kényelem kedvéért feltételezzük, hogy bármelyik ilyen lánc 0 kép.
Q{\ displaystyle Q \!}vs.{\ displaystyle c \!}Q{\ displaystyle Q \!}Q{\ displaystyle Q \!}{0,1}∗{\ displaystyle \ left \ {0,1 \ right \} ^ {*}}én∈én{\ displaystyle i \ in I}Q(én)∈{0,1}{\ displaystyle Q (i) \ in \ bal \ {0,1 \ jobb \}}vs.(én)∈{0,1}∗{\ displaystyle c (i) \ in \ bal \ {0,1 \ jobb \} ^ {*}}Q(én){\ displaystyle Q (i) \!}{0,1}∗{\ displaystyle \ left \ {0,1 \ right \} ^ {*}}
Kapcsolat a döntési problémák és az azokat megoldó algoritmusok között
- Egy algoritmus akkor fogad el egy karakterláncot, ha egy bemenetet kapva az algoritmus kilépNÁL NÉL{\ displaystyle A \!} x∈{0,1}∗{\ displaystyle x \ in \ bal \ {0,1 \ jobb \} ^ {*}}x{\ displaystyle x \!}NÁL NÉL(x)=1{\ displaystyle A (x) = 1 \!}
- Egy algoritmus elutasítja a karakterláncot, ha .NÁL NÉL{\ displaystyle A \!} x{\ displaystyle x \!}NÁL NÉL(x)=0{\ displaystyle A (x) = 0 \!}
Nyelv elfogadott
- Az algoritmus által elfogadott nyelv az algoritmus által elfogadott húrkészlet, azaz .NÁL NÉL{\ displaystyle A \!}L={x∈{0,1}∗:NÁL NÉL(x)=1}{\ displaystyle L = \ left \ {x \ in \ left \ {0,1 \ right \} ^ {*}: A (x) = 1 \ right \}}
A nyelv döntött
- Egy nyelv van határozott egy algoritmus esetleges bitsorozat nem tartozó elutasítja .L{\ displaystyle L \!}NÁL NÉL{\ displaystyle A \!}L{\ displaystyle L \!}NÁL NÉL{\ displaystyle A \!}
Komplexitás osztály és nyelv
Informálisan meghatározhatjuk a komplexitási osztályt olyan nyelvek halmazaként, amelyek tagságát egy algoritmus bonyolultságának mértéke határozza meg, amely meghatározza, hogy egy adott karakterlánc tartozik-e a nyelvhez . Így a bonyolultsági osztály úgy definiálható, mint egy olyan nyelvkészlet, amelyen egy polinom idő algoritmus dönt.
x{\ displaystyle x \!}L{\ displaystyle L \!}P{\ displaystyle P \!}{0,1}∗{\ displaystyle \ left \ {0,1 \ right \} ^ {*}}
Hasznosság
A polinomiális idő redukciójának fogalmát az algoritmusok bonyolultságának elmélete keretében használják a problémák osztályozására. Valóban lehetővé teszi formális módon és polinomiális időben megmutatni, hogy egy probléma legalább olyan nehéz, mint egy másik: ha akkor nem nehezebb , vagy elméletibb módon elmondta: és ugyanaz az osztálya van összetettségűek.
L1≤PL2{\ displaystyle L_ {1} \ leq _ {P} L_ {2}}L1{\ displaystyle L_ {1} \!}L2{\ displaystyle L_ {2} \!}L1{\ displaystyle L_ {1} \!}L2{\ displaystyle L_ {2} \!}
Példák redukcióra
- Részhalmaz-összegig fedezett
- Kattintson a 3-SAT-ra
- SAT-tól 3-SAT-ig
- Részhalmaz-összeg SAT-ba
- 3-SAT kattintással
- 3-SAT a csúcsfedélig
Megjegyzések és hivatkozások
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">