Clasa co-NP

În teoria algoritmilor , este adesea considerată o clasă strâns legată de P și NP , clasa de complemente ale limbajelor din NP numită co-NP .

Definiție formală

Clasa de complexitate co-NP este definită pentru un set de limbi, adică seturi de cuvinte peste un alfabet finit . Un limbaj aparține clasei co-NP dacă există o mașină Turing deterministă M și un polinom p astfel încât . $\Sigma$ $L\subseteq \Sigma ^{*}$ $L=\{x\in \Sigma ^{*}:\forall y,|y|<p(|x|)M(x,y)=0\)$

Relațiile clasei NP cu alte clase

Literatură

Thomas H. Kormen et al.Algorithms : Construction and Analysis = Introduction to Algorithms. - Ed. a II-a. - M . : „Williams” , 2006. - 1296 p. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M . : „Williams” , 2002. - 528 p. - ISBN 0-201-44124-1 .

Clasele de complexitate ale algoritmilor
Considerată ușoară	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-complet ZPP RP BPP BQP EQP APX
Ar trebui să fie dificil	U.P. NP NP complet co-NP co-NP-complet AM M.A._ QMA PH ⊕P PP #P #P IP PSPACE PSPACE-complete
Considerat dificil	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTAR R PR RE RE-completare Co-RE Co-RE-complete TOATE