Co-NP-úplná třída

Co-NP-úplný problém  - v teorii algoritmů problém s odpovědí "ano" nebo "ne" , patřící do třídy co-NP , takže jakýkoli problém z této třídy může být redukován na ni v polynomiálním čase .

Jestliže P ≠ co-NP, pak žádný co-NP-úplný problém nemůže být vyřešen v polynomiálním čase. Pokud lze rychle vyřešit jakýkoli co-NP-úplný problém , pak existuje rychlý algoritmus pro jakýkoli problém ze třídy co-NP.

Jakýkoli co-NP-úplný problém je doplňkem nějakého NP-úplného problému . Existují problémy, které patří jak do třídy NP , tak do třídy co-NP , jako je jakýkoli problém ze třídy P a problém faktorizace . Zároveň není známo, zda se třídy NP a co-NP shodují, nebo ekvivalentně, zda existuje problém, který je NP- i co-NP-úplný.

Formální definice

Problém řešitelnosti je ko-NP-úplný, pokud sám patří do třídy co-NP a jakýkoli jiný ko-NP problém je na něj polynomiálně redukovatelný . Jinými slovy, pro jakýkoli problém z třídy co-NP existuje algoritmus, který v polynomiálním čase transformuje vstupní data problému na vstupní data problému takovým způsobem, že se odpověď na nový problém shoduje. s odpovědí na tu původní. Pokud tedy existuje polynomiální algoritmus pro problém, pak jakýkoli problém ze třídy co-NP lze vyřešit v polynomiálním čase.

Příklad

Jedním jednoduchým příkladem ko-NP-úplného problému je testování booleovského vzorce pro tautologii . Tedy zda pro všechny množiny proměnných platí daný vzorec. Tento problém úzce souvisí s problémem splnitelnosti , ve kterém potřebujeme zjistit, zda alespoň jedna taková množina proměnných existuje.

Literatura

• Cormen T. Leizerson C. Rivest R. Algoritmy: Konstrukce a analýza: Učebnice: per. z angličtiny. . — Moskva MTsNMO. Archivováno 21. srpna 2019 na Wayback Machine