Cook – Levinova věta - Cook–Levin theorem

v teorie výpočetní složitosti, Cook – Levinova věta, také známý jako Cookova věta, uvádí, že Booleovský problém uspokojivosti je NP-kompletní. To znamená, že je v NP a jakýkoli problém v NP může být snížena v polynomiálním čase o a deterministický Turingův stroj k problému s booleovskou uspokojivostí.

Věta je pojmenována po Stephen Cook a Leonid Levin.

Důležitým důsledkem této věty je, že pokud existuje deterministický polynomiální časový algoritmus pro řešení booleovské uspokojivosti, pak každý NP problém lze vyřešit pomocí deterministického polynomiálního časového algoritmu. Otázka, zda takový algoritmus pro booleovskou uspokojivost existuje, je tedy ekvivalentní s Problém P versus NP, který je obecně považován za nejdůležitější nevyřešený problém v teoretické informatice.

Příspěvky

Koncept NP-úplnost byl vyvinut koncem šedesátých a počátkem sedmdesátých let souběžně výzkumníky v USA a USA SSSR V USA v roce 1971 Stephen Cook publikoval příspěvek „Složitost postupů dokazování věty“^[1] v sborníku konference nově založené ACM Symposium on Theory of Computing. Richard Karp následující příspěvek „Reducibilita mezi kombinatorickými problémy“,^[2] vygeneroval obnovený zájem o Cookovy noviny poskytnutím seznam 21 NP-úplných problémů. Cook a Karp obdrželi a Turing Award pro tuto práci.

Teoretický zájem o úplnost NP byl také zvýšen prací Theodora P. Bakera, Johna Gilla a Robert Solovay který ukázal, že řešení NP-problémů v Stroj Oracle modely vyžaduje exponenciální čas. To znamená, že existuje věštec A taková, že pro všechny subexponenciální deterministické třídy časové složitosti T je relativizovaná třída složitosti NP^A není podmnožinou T^A. Zejména pro toto věštce, P^A ≠ NP^A.^[3]

V SSSR byl výsledek ekvivalentní Bakerovi, Gill a Solovayovi publikován v roce 1969 M. Dekhtiarem.^[4] Později Levin příspěvek „Problémy s univerzálním vyhledáváním“,^[5] byla zveřejněna v roce 1973, ačkoli byla zmíněna v rozhovorech a předložena ke zveřejnění o několik let dříve.

Levinův přístup se mírně lišil od přístupu Cooka a Karpa v tom, že uvažoval problémy s hledáním, které vyžadují hledání řešení, nikoli pouhé určení existence. Poskytl 6 takových NP-úplných problémů s hledáním, nebo univerzální problémyNavíc pro každý z těchto problémů našel algoritmus, který jej řeší v optimálním čase (zejména tyto algoritmy běží v polynomiálním čase právě tehdy P = NP ).

Definice

A rozhodovací problém je v NP pokud to může vyřešit a nedeterministický algoritmus v polynomiální čas.

An instance booleovského problému uspokojivosti je Booleovský výraz který kombinuje Booleovské proměnné použitím Booleovské operátory.

Výraz je uspokojivý pokud existuje nějaký úkol pravdivostní hodnoty k proměnným, díky nimž je celý výraz pravdivý.

Idea

Vzhledem k jakémukoli rozhodovacímu problému v NP zkonstruujte nedeterministický stroj, který jej řeší v polynomiálním čase. Potom pro každý vstup do tohoto stroje vytvořte booleovský výraz, který vypočítá, zda je konkrétní vstup předán stroji, stroj běží správně a stroj se zastaví a odpoví „ano“. Potom může být výraz uspokojen tehdy a jen tehdy, pokud existuje způsob, jak stroj správně fungovat a odpovědět „ano“, takže uspokojivost vytvořeného výrazu je ekvivalentní k otázce, zda stroj odpoví „ano“.

Důkaz

Schematizované přijímání výpočtu strojem M.

Tento důkaz je založen na důkazu, který poskytli Garey a Johnson.^[6]

Existují dvě části, které dokazují, že problém s booleovskou uspokojivostí (SAT) je NP-úplný. Jedním z nich je ukázat, že SAT je NP problém. Druhým je ukázat, že každý problém NP lze snížit na instanci problému SAT pomocí a polynomial-time many-one reduction.

SAT je v NP, protože jakékoli přiřazení booleovských hodnot booleovským proměnným, o nichž se tvrdí, že splňují daný výraz, může být ověřeno v polynomiálním čase deterministickým Turingovým strojem. (Prohlášení ověřitelný v polynomiálním čase o a deterministický Turingův stroj a řešitelný v polynomiálním čase o a nedeterministický Turingův stroj jsou naprosto rovnocenné a důkazy lze najít v mnoha učebnicích, například v Sipser's Úvod do teorie výpočtu, oddíl 7.3., jakož i v článku Wikipedie o NP ).

Nyní předpokládejme, že daný problém v NP lze vyřešit pomocí nedeterministický Turingův stroj $M = (Q, Σ, s, F, δ)$ , kde Q je sada stavů, Σ je abeceda páskových symbolů, $s \in Q$ je počáteční stav, $F \subseteq Q$ je množina přijímajících států a $δ ⊆ ((Q \ F) × Σ) × (Q × Σ × {−1, +1})$ je přechodový vztah. Předpokládejme dále M včas přijme nebo odmítne instanci problému p(n) kde n je velikost instance a p je polynomiální funkce.

Pro každý vstup Já, zadáme logický výraz, který je uspokojivý kdyby a jen kdyby stroj M přijímá Já.

Booleovský výraz používá proměnné uvedené v následující tabulce. Tady, $q \in Q, - p (n) \leq i \leq p (n), j \in Σ$ , a $0 \leq k \leq p (n)$ .

Proměnné	Zamýšlený výklad	Kolik?
T_{i, j, k}	Pravda, pokud je buňka pásky i obsahuje symbol j v kroku k výpočtu.	Ó(p(n)²)
H_{já, k}	Je pravda, pokud MČtecí / zapisovací hlava je na buňce pásky i v kroku k výpočtu.	Ó(p(n)²)
Q_{q, k}	Pravda, pokud M je ve stavu q v kroku k výpočtu.	Ó(p(n))

Definujte logický výraz B být spojení dílčích výrazů v následující tabulce pro všechny $- p (n) \leq i \leq p (n)$ a $0 \leq k \leq p (n)$ :

Výraz	Podmínky	Výklad	Kolik?
${ displaystyle T_ {i, j, 0}}$	Cela s páskou i zpočátku obsahuje symbol j	Počáteční obsah pásky. Pro i > n-1 a i <0, mimo skutečný vstup ${ displaystyle I}$ , počáteční symbol je speciální výchozí / prázdný symbol.	Ó(p(n))
${ displaystyle Q_ {s, 0}}$		Počáteční stav M.	1
${ displaystyle H_ {0,0}}$		Počáteční poloha čtecí / zapisovací hlavy.	1
${ displaystyle neg T_ {i, j, k} lor neg T_ {i, j ', k}}$	j ≠ j '	Maximálně jeden symbol na buňku pásky.	Ó(p(n)²)
${ displaystyle bigvee _ {j in Sigma} T_ {i, j, k}}$		Alespoň jeden symbol na buňku pásky.	Ó(p(n)²)
${ displaystyle T_ {i, j, k} přistát T_ {i, j ', k + 1} rightarrow H_ {i, k}}$	j ≠ j '	Páska zůstane beze změny, pokud není napsána.	Ó(p(n)²)
¬Q_{q, k} ∨ ¬Q_{q ', k}	q ≠ q '	Pouze jeden stát najednou.	Ó(p(n))
¬H_{já, k} ∨ ¬H_{i ', k}	i ≠ já ′	Pouze jedna poloha hlavy najednou.	Ó(p(n)³)
${ displaystyle { begin {array} {l} (H_ {i, k} land Q_ {q, k} land T_ {i, sigma, k}) to bigvee _ {((q , sigma), (q ', sigma', d)) in delta} (H_ {i + d, k + 1} land Q_ {q ', k + 1} land T_ {i , sigma ', k + 1}) end {pole}}}$	k<p(n)	Možné přechody v kroku výpočtu k když je hlava v poloze i.	Ó(p(n)²)
${ displaystyle bigvee _ {0 leq k leq p (n)} bigvee _ {f in F} Q_ {f, k}}$		Musí skončit v přijímajícím stavu, nejpozději v kroku p(n).	1

Pokud existuje akceptující výpočet pro M na vstupu Já, pak B je uspokojivý zadáním T_{i, j, k}, H_{já, k} a Q_{já, k} jejich zamýšlené interpretace. Na druhou stranu, pokud B je uspokojivý, pak existuje přijatelný výpočet pro M na vstupu Já který následuje kroky označené přiřazením k proměnným.

Existují Ó(p(n)²) Booleovské proměnné, každá kódovatelná v prostoru $Ó (log p (n))$ . Počet klauzulí je Ó(p(n)³) takže velikost B je Ó(log (p(n))p(n)³). Transformace je tedy podle potřeby jistě polynomiální redukcí typu mnoho-jedna.

Důsledky

Důkaz ukazuje, že jakýkoli problém v NP lze snížit v polynomiálním čase (ve skutečnosti stačí logaritmický prostor) na instanci booleovského problému uspokojivosti. To znamená, že pokud by problém booleovské uspokojivosti mohl být vyřešen v polynomiálním čase pomocí a deterministický Turingův stroj, pak by všechny problémy v NP mohly být vyřešeny v polynomiálním čase, a tak třída složitosti NP by se rovnal třídě složitosti P.

Význam úplnosti NP byl objasněn publikací v roce 1972 Richard Karp „Mezník“, „Reducibilita mezi kombinatorickými problémy“, ve kterém to ukázal 21 různorodých kombinatorických a grafických teoretických problémů, každý nechvalně známý svou neřešitelností, jsou NP-kompletní.^[2]

Karp ukázal, že každý z jeho problémů je NP-úplný snížením dalšího problému (již se ukázalo, že je NP-úplný) na tento problém. Například ukázal problém 3SAT ( Booleovský problém uspokojivosti pro výrazy v konjunktivní normální forma s přesně třemi proměnnými nebo negacemi proměnných na klauzuli), které mají být NP-úplné tím, že ukazují, jak snížit (v polynomiálním čase) jakoukoli instanci SAT na ekvivalentní instanci 3SAT. (Nejprve upravíte důkaz Cook-Levinovy věty tak, aby výsledný vzorec byl v konjunktivní normální formě, pak zavedete nové proměnné k rozdělení vět s více než 3 atomy. Například klauze (A ∨ B ∨ C ∨ D) lze nahradit spojením vět (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D), kde Z je nová proměnná, která se ve výrazu nepoužije nikde jinde. Klauzule s méně než 3 atomy lze polstrovat; například A lze nahradit (A ∨ A ∨ A) a (A ∨ B) lze nahradit (A ∨ B ∨ B)).

Garey a Johnson ve své knize představili více než 300 NP-úplných problémů Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti,^[6] a stále se objevují nové problémy v této třídě složitosti.

Ačkoli mnoho praktických případů SAT může být řešeno heuristickými metodami Otázka, zda existuje deterministický algoritmus polynomiálního času pro SAT (a následně všechny ostatní NP-úplné problémy), je stále slavným nevyřešeným problémem, a to navzdory desetiletím intenzivního úsilí teoretiků složitosti, matematických logiků a dalších. Další podrobnosti najdete v článku Problém P versus NP.

Reference

^ Cook, Stephen (1971). „Složitost postupů dokazování věty“. Proceedings of the Third Annual ACM Symposium on Theory of Computing. str. 151–158. doi:10.1145/800157.805047.
^ ^A ^b Karp, Richard M. (1972). „Reducibilita mezi kombinatorickými problémy“ (PDF). Raymond E. Miller; James W. Thatcher (eds.). Složitost počítačových výpočtů. New York: Plenum. str. 85–103. ISBN 0-306-30707-3.
^ T. P. Baker; J. Gill; R. Solovay (1975). "Relativizace otázky P = NP". SIAM Journal on Computing. 4 (4): 431–442. doi:10.1137/0204037.
^ Dekhtiar, M. (1969). "O nemožnosti vyloučit vyčerpávající vyhledávání při výpočtu funkce ve vztahu k jejímu grafu". Sborník Akademie věd SSSR (v Rusku). 14: 1146–1148.
^ Levin, Leonid (1973). „Универсальные задачи перебора“ [Problémy s univerzálním vyhledáváním]. Problémy přenosu informací (v Rusku). 9 (3): 115–116. Přeložil do angličtiny Trakhtenbrot, B. A. (1984). „Průzkum ruských přístupů k Perebor (vyhledávání hrubou silou) ". Annals of the History of Computing. 6 (4): 384–400. doi:10.1109 / MAHC.1984.10036.
^ ^A ^b Garey, Michael R .; David S. Johnson (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. W. H. Freeman. ISBN 0-7167-1045-5.

[1] Cook, Stephen (1971). „Složitost postupů dokazování věty“. Proceedings of the Third Annual ACM Symposium on Theory of Computing. str. 151–158. doi:10.1145/800157.805047.

[Karp-2] A ^b Karp, Richard M. (1972). „Reducibilita mezi kombinatorickými problémy“ (PDF). Raymond E. Miller; James W. Thatcher (eds.). Složitost počítačových výpočtů. New York: Plenum. str. 85–103. ISBN 0-306-30707-3.

[3] T. P. Baker; J. Gill; R. Solovay (1975). "Relativizace otázky P = NP". SIAM Journal on Computing. 4 (4): 431–442. doi:10.1137/0204037.

[4] Dekhtiar, M. (1969). "O nemožnosti vyloučit vyčerpávající vyhledávání při výpočtu funkce ve vztahu k jejímu grafu". Sborník Akademie věd SSSR (v Rusku). 14: 1146–1148.

[5] Levin, Leonid (1973). „Универсальные задачи перебора“ [Problémy s univerzálním vyhledáváním]. Problémy přenosu informací (v Rusku). 9 (3): 115–116. Přeložil do angličtiny Trakhtenbrot, B. A. (1984). „Průzkum ruských přístupů k Perebor (vyhledávání hrubou silou) ". Annals of the History of Computing. 6 (4): 384–400. doi:10.1109 / MAHC.1984.10036.

[Garey-6] A ^b Garey, Michael R .; David S. Johnson (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. W. H. Freeman. ISBN 0-7167-1045-5.

[1]

[2]

[3]

[4]

[5]

[6]