Cooke-Levinova věta

Cooke-Levinův teorém (také jen Cookův teorém ) říká, že problém splnitelnosti pro booleovskou formuli v CNF ( SAT ) je NP-úplný .

Důkaz tohoto teorému, který získal Stephen Cook ve své základní práci v roce 1971 , byl jedním z prvních důležitých výsledků teorie NP-úplných problémů. Nezávisle ve stejné době tuto větu dokázal sovětský matematik Leonid Levin [1] .

V důkazu Cookovy věty je každý problém z třídy NP výslovně redukován na SAT. S. Cook definoval třídu NP problémů rozpoznávání vlastností následovně. Úloha patří do třídy NP, pokud:

  1. řešením problému je jedna ze dvou odpovědí: „ano“ nebo „ne“ ( problém s rozpoznáváním vlastností );
  2. požadovanou odpověď lze získat na nedeterministickém výpočetním zařízení v polynomiálním čase.

Tato třída, jak později ukázal R. Karp, zase obsahuje další širokou třídu problémů, nazvanou Karpem NP-complete problems , neboli NPC, redukované jedna na druhou v rámci této třídy.

Poté, co se objevily Cookovy výsledky, byla NP-úplnost prokázána u mnoha dalších problémů. V tomto případě se nejčastěji pro prokázání NP-úplnosti určitého problému zadává polynomiální redukce problému SAT na daný problém, případně v několika krocích, tedy pomocí několika meziproblémů.

Poznámky

  1. ↑ L. A. Levin. Univerzální enumerační  problémy // Problémy přenosu informací. - 1973. - T. 9 , č. 3 . - S. 115-116 . Archivováno z originálu 10. října 2017.

Odkazy