Cook tétele
Az elméleti számítógép-tudomány , pontosabban komplexitás elmélet , Cook-tétel is nevezik Cook-Levin -tétel a tétel , amely azt állítja, hogy a SAT probléma , vagyis a probléma kielégíthetőség egy képlet a propozicionális logika , az NP-teljes . Bizonyítottuk, 1971 által Stephen Cook , és sokkal ugyanakkor a Leonid Levin .
Ez az eredmény azért fontos, mert ha megmutatjuk, hogy van egy polinomiális időalgoritmus a SAT feladatra, akkor a P = NP probléma megoldódik. Ez az eredmény ráadásul sok más probléma NP-keménységét is megmutatja polinomiális redukcióval .
Definíciók
A döntési probléma van NP ha nem-determinisztikus Turing-gép úgy dönt, hogy polinomiális időben.
A döntési probléma az NP-teljes , ha az NP és ha bármilyen probléma NP lehet csökkenteni egy polinom csökkentését .
A SAT példánya egy logikai kifejezés, amely egyesíti a logikai változókat a logikai operátorokkal . Egy kifejezés akkor kielégítő, ha van olyan változó hozzárendelés, amely az egész kifejezést igazsá teszi .
A demonstráció ötlete
A SAT probléma az NP-ben van, mert a következő, nem determinisztikus Turing-gép dönt polinomiális időben:
- Olvassa el a logikai kifejezést φ;
- A in-ben megjelenő bármely p változóhoz válasszon nem determinisztikusan egy v (p) értéket a (z) {0, 1} mezőben;
- Fogadja el, ha a v értékelés megfelel φ; másként tagadja meg.
Annak bemutatására, hogy a SAT probléma NP-nehéz, az A problémát vesszük figyelembe az NP-ben. Létezik tehát egy nem determinisztikus M Turing-gép, amely polinomiális időben dönti el: az A bármelyik x-ös példánya esetében x csak akkor pozitív A-példa, ha létezik M elfogadó végrehajtása x-szel az polinom hossza | x | -ban. Az elképzelés tehát egy polinom idő alatt hatékonyan felépíteni egy Boole-képletet φ (x), amely intuitív módon azt mondja: „létezik egy elfogadó M végrehajtás x-szel a | x | ". Így x csak akkor pozitív A-példány, ha φ (x) kielégíthető. Így az A polinomiális redukciója van SAT-ban: a SAT ezért NP-kemény.
Demonstráció
A SAT probléma az NP-ben van.
Tegyük fel, hogy az NP-ben egy problémát egy nem determinisztikus Turing-gép old meg M = ( Q , Σ , s , F , δ ) (Q-val az állapothalmaz, Σ a sáv szimbólum ábécéje, s ∈ Q a kezdőbetű állapot, F ⊆ Q a végállapotok halmaza és δ ⊆ (( Q × Σ ) × ( Q × Σ × {−1, + 1})) átmenetek halmaza) és olyan, hogy M elfogadja vagy elutasítja a p ( n ) időbeli probléma, ahol n a példány mérete és p egy polinom függvény.
Minden egyes I példány esetében egy logikai kifejezés, amely akkor és akkor teljesül, ha az M gép elfogadja az I-t .
A logikai kifejezés az alábbi táblázatból vett változókból áll, ahol q ∈ Q , - p ( n ) ≤ i ≤ p ( n ), j ∈ Σ és 0 ≤ k ≤ p ( n ):
| Változók | Értelmezés | Hogyan ? |
|---|---|---|
| T ijk | Igaz, ha a szalag i cellája tartalmazza a j szimbólumot a számítás k lépésében . | O ( p ( n ) ²) |
| H ik | Igaz, ha M olvasási / írási feje a szalag i nyílásában van a számítás k lépésében . | O ( p ( n ) ²) |
| Q qk | Igaz, ha M a számítás k lépésében q állapotban van . | O ( p ( n )) |
Definiáljuk a logikai kifejezés B , mint a összefüggésben a kikötések a következő táblázatban, valamennyi - p ( n ) ≤ i ≤ p ( n ) és a 0 ≤ K ≤ p ( n ):
| Záradékok | Felhasználási feltételek | Értelmezés | Hogyan ? |
|---|---|---|---|
| T ij0 | Az I. bejegyzés i cellája a j szimbólumot tartalmazza . | A szalag kezdeti tartalma. | O ( p ( n )) |
| Q s0 | Az M kezdeti tartalma | O (1) | |
| H 00 | Az olvasó / író fej kiinduló helyzete. | O (1) | |
| T ijk → ¬ T ij′k | j ≠ j ′ | Cellánként egy szimbólum. | O ( p ( n ) ²) |
| T ijk = T ij ( k +1) ∨ H ik | A szalag változatlan marad, amíg meg nem írták. | O ( p ( n ) ²) | |
| Q qk → ¬ Q q′k | q ≠ q ′ | Egyszerre csak egy állam. | O ( p ( n )) |
| H ik → ¬ H i′k | i ≠ i ′ | Egyszerre egy fej helyzet a szalagon. | O ( p ( n ) ³) |
| A tagmondatok ( H ik ∧ Q qk ∧ T iσk ) → ( H ( i + d ) ( k + 1) ∧ Q q ( k + 1) ∧ T iσ ' ( k + 1) ) tagozódása |
( q , σ , q ′ , σ ′ , d ) ∈ δ | Lehetséges átmenetek a k lépésben, amikor a fej i helyzetben van . | O ( p ( n ) ²) |
| A Q f ( p ( n )) tagmondatok elkülönülése |
f ∈ F . | Elfogadó állapotban kell befejeznie . | O (1) |
Ha van elfogadható számítás M számára az I bemenetre , akkor B kielégítő, hozzárendelve T ijk , H ik és Q ik értelmezéseiket. Másrészt, ha B kielégítő, akkor elfogadható számítás van az M számára az I bemenettel , amely a változók hozzárendelésével jelzett lépéseket követi.
Vannak O ( p ( n ) 2 ) logikai változók, amelyek mindegyike O méretben kódolható (log p ( n )). A tagmondatok száma O ( p ( n ) 3 ). Tehát B mérete O ((log p ( n )) p ( n ) 3 ). Ez n- nél polinom , a bejegyzés mérete; ezért az átalakítás szükség szerint polinom.
Következmények
A bizonyíték azt mutatja, hogy az NP minden problémája polinomiális idő alatt csökkenthető (valójában a LOGSPACE elegendő) egy SAT példányig. Ez azt mutatja, hogy ha a SAT polinomiális időben megoldható egy Turing-géppel ( ezúttal determinisztikus ), akkor az NP összes problémája megoldható polinomiális időben. Tehát a komplexitási osztály egyenlő lenne P. komplexitásával.
Cook tétele az NP-teljesség első bizonyítéka. Az NP-teljesség további bizonyítékai általában egy NP-teljesnek minősített probléma polinomiális redukciójával történnek . Például bebizonyíthatjuk, hogy a 3-SAT probléma (az a SAT probléma, ahol az egyes tagmondatok legfeljebb három változóból (vagy azok negációjából) állnak konjunktív normál alakban ) NP-teljes, ha bemutatjuk a SAT redukcióját egy példány ekvivalensre 3-SAT.
Garey és Johnson több mint 300 NP-teljes problémát mutat be, és az új problémákat mindig osztályozás céljából vizsgálják.
Hivatkozások
(fr) Ez a cikk részben vagy egészben a „ Cook - Levin tétel ” című angol Wikipedia cikkből származik ( lásd a szerzők felsorolását ) .- (in) Stephen Cook , összetettsége tételbizonyítás eljárások , Proceedings of the ACM harmadik éves szimpózium Theory of Computing (1971), 151-158 oldalak.
- (in) Leonid Levin , " univerzális kereső problémák ( orosz : Универсальные задачи перебора , Universal'nye perebornye zadachi) " , problémái információ átvitel ( orosz : Проблемы передачи информации , Problemy Peredachi INFORMATSII) , vol. 9, n o 3,1973, P. 115–116 [PDF] (ru) , angol nyelvre fordította (en) BA Trakhtenbrot , „ A felmérés az orosz megközelítésekről a perebor (brute-force keresés) algoritmusokra ” , Annals of the History of Computing , vol. 6, n o 4,1984, P. 384–400 ( DOI 10.1109 / MAHC.1984.10036 ).
- (in) Michael Garey és David S. Johnson , Számítógépek és kezelhetetlen: A Guide to the Theory of NP-teljessége , Freeman, 1979 ( ISBN 0-7167-1045-5 ) .