coNP

定義

$ \textbf{coNP} := \overline{\mathbf{NP}}

または

$ x \in L \iff \forall u \in 2^{p(|x|)}. [M(\langle x, u \rangle) = 1]

性質

$ \textbf{P} \subseteq \textbf{NP} \cap \textbf{coNP}

$ \textbf{P} = \textbf{NP} \Rightarrow \textbf{NP} = \textbf{coNP}