Cook-Levinova věta

Cookova věta

• Problém SAT je NP-úplný.

Název: SAT (problém splnitelnosti booleovských formulí) Vstup: Booleovská formule v konjunktivní normální formě. Otázka: Je daná formule splnitelná?

• Víme že SAT patří do $NPTIME$, protože existuje nedeterministický polynomiální algoritmus, který jej řeší

• Musíme dokázat, že je také NP-těžký

• Myšlenka důkazu:

  • Základní myšlenkou důkazu je ukázat, že existuje polynomiální, univerzální TS, který může simulovat libovolný nedeterministický algoritmus v polynomiálním čase.
  • Tento stroj pak může být použit k převedení libovolného problému v NP na SAT

Důkaz

• Musíme dokázat $\forall P\in NPTIME:P{\le }_{p}SAT$, o každém problému $P$ víme, že je reprezentován nedeterministickým TS.
• Ukážeme konstrukci, která pro TS $M$ a vstupní slovo $w$ sestrojí formuli ${\psi }_{M,w}$, tak že formule ${\psi }_{M,w}$ bude splnitelná právě tehdy, když TS přijme slovo $w$
• Výpočet TS $M$ na vstupním slově $w(|w|=n)$ můžeme reprezentovat tabulkou
  • Zavedeme proměnné
    • $x_{i,j,(q,s)}$ pro každé $0\le i\le n^k$ (konfigurace = řádek),
    • $0\le j\le n^k$ (pozice symbolu = sloupec),
    • $s\in \Gamma$ (páskový symbol).
  • Zavedeme proměnné
    • $x_{i,j,(q,s)}$ pro každé $0\le j\le n^k$,
    • $0\le j\le n^k$,
    • $s\in \Gamma$,
    • $q\in Q$ (stav).
• Formuli ${\psi }_{M,w}$ vytvoříme jako (musí splňovat podmínky) ${\psi }_{M,w}={\psi }_{cell}\wedge {\psi }_{start}\wedge {\psi }_{move}\wedge {\psi }_{accept}$
  • ${\psi }_{cell}$ musí zajistit, že v každé buňce tabulky je právě jeden symbol
  • ${\psi }_{start}$ musí zajistit, že první řádek odpovídá počáteční konfiguraci
  • ${\psi }_{accept}$ musí zajistit, že na posledním řádku tabulky se vyskytuje stav $q_{ANO}$. (Předpokládáme, že pokud TS skončí výpočet dřív než po $n^k$ krocích, všechny následující konfigurace (řádky tabulky) jsou stejné)
  • ${\psi }_{move}$ musí zajistit, že každé následující konfigurace vznikne z předchozí správným způsobem.
• Formule ${\psi }_{M,w}={\psi }_{cell}\wedge {\psi }_{start}\wedge {\psi }_{move}\wedge {\psi }_{accept}$ je polynomiální vzhledem k $n$.
• Jestliže je splnitelná tato formule, dokážeme vyplnit tabulku tak, že reprezentuje přijímající výpočet TS $M$ na slově $w$. (Jestliže je formule nesplnitelná, tak neexistuje přijímající výpočet TS $M$ na slově $w$, protože se nám nepodaří vyplnit tabulku reprezentující takový výpočet.)
• Ukázali jsme tedy polynomiální převod libovolného problému z NP na problém SAT

Navigace

Předchozí: NP-úplné problémy Následující: Příklady NP-úplných problémů, dokazování NP-úplnosti Celý okruh: 1. Teoretické základy informatiky