Csökkentés (bonyolultság)

A kiszámíthatóság és a komplexitás elméletében a redukció olyan algoritmus, amely egy algoritmikus probléma példányát egy másik probléma egyik (vagy több) példányává alakítja. Ha ilyen csökkenés történik az A problémáról a B problémára, akkor azt mondjuk, hogy az A probléma a B problémára redukálódik. Ebben az esetben a B probléma nehezebb, mint az A probléma, mivel egy problémát megoldhatunk az alkalmazással a redukció és a B feladat algoritmusa. Ezután írunk egy ≤ B-t .

A csökkentéseknek kétféle célja van.

• Mutassa meg, hogy egy probléma eleve nehéz. Például redukcióval mutatjuk be, hogy a problémák eldönthetetlenek  : ezután megmutatjuk, hogy a probléma annyira algoritmikusan nehéz, hogy nincs olyan algoritmikus, amely eldöntené. A polinom redukciókat arra használjuk, hogy bemutassuk, hogy a problémák NP-nehézek. Általánosabban, csökkentésekkel bizonyítják, hogy a probléma a komplexitás egyik legnehezebb osztálya .
• Mutassa meg, hogy egy probléma könnyen megoldható algoritmikusan. Például, ha A ≤ B a ≤ polinomiális idő csökkenésével, és B P-hez tartozik , akkor A szintén P-ben van .

Bevezető példa

Vegyünk két problémát: két egész szám szorzásának M feladatát és egy egész szám négyzetének C feladatát. C. A probléma könnyebb, mint a probléma M. Sőt, ha tudjuk szorzás, akkor megemelheti a szám négyzetes szorozni is, így a C ≤ M . A C csökkentése M-ben  : egy négyzetre kerülő egész számot átalakítunk két egyenlő egész szám (x, x) szorzatává. x↦(x,x){\ displaystyle x \ mapsto (x, x)}

Érdekes módon azt is megmutathatjuk, hogy M redukálódik C-re ( M ≤ C ). Valóban, a képletnek köszönhetően:

nál nél×b=(nál nél+b)2-nál nél2-b22{\ displaystyle a \ times b = {\ frac {\ bal (a + b \ jobb) ^ {2} -a ^ {2} -b ^ {2}} {2}}}

látjuk, hogy kiszámíthatjuk az a és b szorzatát, három négyzetmagasság kiszámításával. Így a két probléma egyformán nehéz (egymásba redukálhatók).

Definíciók

A következő definíciók egész számokat tartalmaznak, mivel a problémák példányai ℕ-be vannak kódolva.

Mivel két természetes egész számok A és B , és egy sor funkciók F a ℕ hogy ℕ, lezárt készítményt, A azt mondják, hogy redukálható B által F , ha:∃f∈F . ∀x∈NEM . x∈NÁL NÉL⇔f(x)∈BA {\ displaystyle \ létezik f \ az F {\ mbox {fájlban. }} \ forall x \ in \ mathbb {N} {\ mbox {. }} x \ A-ban \ Baloldali nyíl f (x) \ B-ben}

Megírtuk . NÁL NÉL≤FB{\ displaystyle A \ leq _ {F} B}

Legyen S a P (ℕ) és ≤ redukció részhalmaza , akkor azt mondják, hogy S ≤∀s∈S . ∀NÁL NÉL∈P(NEM) . NÁL NÉL≤s⇒NÁL NÉL∈S{\ displaystyle \ forall s \ az S {\ mbox {fájlban. }} \ összes A \ P-ben (N) {\ mbox {. }} A \ leq s \ Rightarrow A \ in S}

Állítólag az A A részhalmaz S számára nehéz , ha ∀s∈S . s≤NÁL NÉL{\ displaystyle \ forall s \ az S {\ mbox {fájlban. }} s \ leq A}

Végül egy részhalmaza Egy az N mondják teljes számára S ha A nehéz O és A tartozik S .

Példák

Annak bizonyítására, hogy egy probléma NP-teljes , egy ismert NP-teljes problémát (például SAT-problémát ) polinomiális redukcióval redukálhatunk erre a problémára .

A kiszámíthatóság terén például bizonyíthatjuk Rice tételét a megállítási probléma csökkentésével .

A redukció típusai

A redukciónak több típusa van.

• Turing redukció
• Cook kedvezménye
• Polinomiális időcsökkentés
• A logaritmikus tér csökkentése
• Első rendű csökkentés
• A levin redukciók polinomi függvények, amelyek több tanúsítvánnyá alakítják át
• Polinomiális idő redukciója az igazságtáblával: az A problémát polinomiális időben az igazságtábla csökkenti, ha el tudjuk dönteni, hogy x tartozik-e A-hez, azzal, hogy előre kiszámítjuk a B-hez tartozó szavak tagságának számos kérdését, és a kérdéseire adott válaszokon egy logikai képletet írunk le. annak eldöntésére, hogy x tartozik-e A. -hoz. Pontosabban Buss és Hay variánsokat vezet be attól függően, hogy a Boole-képletet szintaktikai fája, áramköre vagy igazságtáblája képviseli-e.
• Csökkentések, amelyek megőrzik az optimalizálási probléma közötti közelítési tényezőt a közelítő algoritmusok területén

Lásd is

Gadget

Megjegyzések és hivatkozások

1. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest és Clifford Stein , Bevezetés az algoritmikába , Dunod ,2002[ a kiadás részlete ] 34. fejezet, NP-teljes
2. (en) Immerman, Leíró összetettség
3. (en) Arora, Barak, számítási komplexitás - modern megközelítést , p. 55
4. (in) "  A polinomiális idő redukálhatóságának összehasonlítása  " , Theoretical Computer Science , vol.  1, n o  21 st december 1975, P.  103-123 ( ISSN  0304-3975 , DOI  10.1016 / 0304-3975 (75) 90016-X , olvasható online , elérhető december 18, 2018 )
5. Samuel R. Buss és Louise Hay , „  Az igazság-asztal redukálhatóságáról SAT-ra  ”, Inf. Comput. , vol.  91, n o  1,1991. március, P.  86-102 ( ISSN  0890-5401 , DOI  10.1016 / 0890-5401 (91) 90075-D , olvasható online , elérhető december 18, 2018 )
6. (en) Vijay V. Vazirani , Közelítő algoritmusok , Springer-Verlag,2003( ISBN  978-3-540-65367-7 , online olvasás ) , A.3.1. Szakasz, 348. o

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">