V teoretické informatice je co-NP (nebo coNP ) třídou složitosti , tj. Souborem rozhodovacích problémů ve smyslu teorie složitosti . Jedná se o doplňkovou třídu (ve smyslu složitosti) třídy NP .
Jsou uvedeny dvě ekvivalentní definice.
co-NP je sada jazyků, které mají pro doplňkový (ve smyslu jazyků) jazyk NP .
Dalším způsobem vidění je, že co-NP je sada jazyků, u nichž může ověřitelný důkaz v polynomiálním čase dokázat, že slovo do jazyka nepatří (protiklady).
Třídu coNP můžete definovat pomocí certifikátů . Na abecedě je jazyk v co-NP, pokud existuje polynom a Turingův stroj v polynomiálním čase , takže pro slovo máme ekvivalenci mezi a skutečnost, že pro jakýkoli certifikát stroj přijímá záznam .
Pokud jde o třídu NP, definujeme pojem co-NP-obtížných problémů . Problém je co-NP-těžký, pokud se jakýkoli problém co-NP redukuje na něj v polynomiálním čase . Problém je co-NP-complete, pokud je v co-NP a je to co-NP obtížné.
Z jakéhokoli problému v NP můžeme sestrojit „dvojí“ problém v co-NP.
Problém v NP | Doplňkový problém v coNP |
---|---|
SAT problém : daný logický vzorec, existuje přiřazení jejích proměnných, které dělá to pravda? | vzhledem k booleovskému vzorci, je nepravdivé pro jakékoli přiřazení jeho proměnných? (i když raději vezmeme v úvahu problém platnosti, který je nesrovnatelný s předchozím problémem: vzhledem k booleovskému vzorci platí pro všechna přiřazení jeho proměnných?) |
Hamiltonian cesta problém : daný graf G , dělá si hamiltonovskou cestu existovat ? | problém neexistence hamiltonovské cesty : vzhledem k grafu G n uzlů a m oblouků, je pravda, že žádná kombinace n oblouků mezi m netvoří hamiltonovskou cestu? |
problém kliky : vzhledem k grafu G a celému číslu k , existuje v G klika o velikosti k ? | problém nekliky: vzhledem k grafu G a celému číslu k , je pravda, že G nemá kliku velikosti k ? |
Otázka co-NP = NP je otevřená otázka, ale předpokládá se, že tyto třídy se liší. Pokud P = NP , pak NP = co-NP, ale konverzace není známa.
Víme to , ale rovnost je otevřená otázka. Je známo, že problém rozkladu produktu hlavního faktoru je v NP a co-NP, ale obecně se předpokládá, že není v P.
V polynomiální hierarchii odpovídá co-NP prvnímu existenčnímu stupni: co-NP = .
V teorii složitosti se říká, že problém je co-NP-úplný, pokud je co-NP a pokud je nějaký problém co-NP redukovatelný v polynomiálním čase na něj. Jinými slovy, je to třída úplných problémů odpovídajících co-NP . Jakýkoli problém s úplným NP je doplněním problému s NP-úplností.
(en) Sanjeev Arora a Boaz Barak , Výpočetní složitost: moderní přístup , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 2.6 („co-NP, EXP a NEXP“)
(fr) Třída co-NP v komplexu Zoo