Třída co-NP

V teorii algoritmů je často zvažována třída úzce související s P a NP , třída doplňků jazyků z NP nazývaná co-NP .

Formální definice

Třída složitosti co-NP je definována pro sadu jazyků, tj. sady slov v konečné abecedě . Jazyk patří do třídy co-NP, pokud existuje deterministický Turingův stroj M a nějaký polynom p takový, že . $\Sigma$ $L\subseteq \Sigma ^{*}$ ${\displaystyle L=\{x\in \Sigma ^{*}:\forall y,|y|<p(|x|)M(x,y)=0\))$

Vztahy třídy NP s ostatními třídami

Literatura

Thomas H. Kormen a kol. , Algoritmy: Konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - M .: "Williams" , 2006. - 1296 s. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Třídy složitosti algoritmů
Považováno za světlo	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-kompletní ZPP RP BPP BQP EQP APX
Prý to bude těžké	U.P. NP NP kompletní co-NP co-NP-kompletní AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-complete
Považováno za obtížné	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete VŠECHNY