191 Complexity — Co NP

191.1 Overview

This module introduces the class \(\mathsf{coNP}\) of complements of \(\mathsf{NP}\) languages [AB09, Definition 2.19] and proves its equivalent characterization by universally quantified polynomial-length certificates [AB09, Definition 2.20, Exercise 2.24]. Along the way it shows that \(\mathsf{P}\) is closed under complement, and records the standard facts \(\mathsf{P} \subseteq \mathsf{NP} \cap \mathsf{coNP}\) [AB09, Exercise 2.23] and \(\mathsf{P} = \mathsf{NP} \Rightarrow \mathsf{NP} = \mathsf{coNP}\) [AB09, Exercise 2.25].

191.2 Declarations

Definition 191.1 The class \(\mathsf{coNP}\)

✓

A language \(L \subseteq \{ 0,1\} ^{*}\) is said to belong to the class coNP when its complement \(\overline{L} = \{ 0,1\} ^{*} \setminus L\) belongs to \(\mathsf{NP}\).

Theorem 191.2 \(\mathsf{P}\) is closed under complement

✓

Let \(L \subseteq \{ 0,1\} ^{*}\) be a language decidable in polynomial time, i.e. \(L \in \mathsf{P}\). Then its complement \(\overline{L} = \{ 0,1\} ^{*} \setminus L\) is also in \(\mathsf{P}\).

Theorem 191.3 Universal-certificate characterization of \(\mathsf{coNP}\)

✓

A language \(L \subseteq \{ 0,1\} ^{*}\) belongs to the class coNP (that is, its complement lies in \(\mathsf{NP}\)) if and only if there exist natural numbers \(C\) and \(c\) and a verifier language \(V \in \mathsf{P}\) such that for every binary string \(x\),

\[ x \in L \iff \text{for every } u \in \{ 0,1\} ^{*} \text{ with } |u| = C \cdot (|x|+1)^{c},\ \ xu \in V, \]

where \(xu\) denotes the concatenation of \(x\) and \(u\).

Theorem 191.4 \(\mathsf{P} \subseteq \mathsf{NP} \cap \mathsf{coNP}\)

✓

Every language \(L \subseteq \{ 0,1\} ^{*}\) in \(\mathsf{P}\) (decidable in polynomial time) lies both in \(\mathsf{NP}\) and in coNP, where coNP is the class of languages whose complement is in \(\mathsf{NP}\); that is, \(\mathsf{P}\) is contained in the intersection of \(\mathsf{NP}\) and coNP.

Theorem 191.5 If \(\mathsf{P} = \mathsf{NP}\) then \(\mathsf{NP} = \mathsf{coNP}\)

✓

If the class \(\mathsf{P}\) of polynomial-time decidable binary languages equals \(\mathsf{NP}\), then \(\mathsf{NP}\) equals coNP, where coNP is the class of languages \(L \subseteq \{ 0,1\} ^{*}\) whose complement \(\{ 0,1\} ^{*} \setminus L\) is in \(\mathsf{NP}\).