Co-NP-luokka

Algoritmiteoriassa ajatellaan usein luokkaa , joka liittyy läheisesti P :hen ja NP :hen, NP :n kielten komplementtien luokkaa, jota kutsutaan co-NP:ksi .

Muodollinen määritelmä

Co-NP-kompleksisuusluokka on määritelty kielijoukolle, eli äärellisen aakkoston sanajoukoille . Kieli kuuluu co-NP-luokkaan, jos on olemassa deterministinen Turingin kone M ja jokin polynomi p siten, että . $\Sigma$ $L\subseteq \Sigma ^{*}$ ${\displaystyle L=\{x\in \Sigma ^{*}:\forall y,|y|<p(|x|)M(x,y)=0\))$

Luokan NP suhteet muihin luokkiin

Kirjallisuus

Thomas H. Kormen ym. Algoritmit: Rakentaminen ja analyysi = Algoritmien johdatus. - 2. painos - M . : "Williams" , 2006. - 1296 s. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Algoritmien monimutkaisuusluokat
Kevyenä pidetty	DLOGTIME AC 0 ACC 0 TC0 [ fi L SL RL NL NC SC CC P P-täydellinen ZPP RP BPP BQP EQP APX
Taitaa olla vaikeaa	U.P. NP NP valmis co-NP co-NP-täydellinen AM M.A. QMA PH ⊕P PP #P #P - IP_ PSPACE PSPACE-täydellinen
Vaikeaksi pidetty	EXPTIME NEXPTIME EXPACE 2-EXPTIME ELEMENTARY R PR RE täytä uudelleen Co-RE Co-RE-complete KAIKKI