Suppose \(B\) is a polynomial-time
certifier. Decision problems can be defined by their YES-instances. The
decision problems in the following complexity classes can be defined
as:
A problem in P: \(\{x : B(x, \epsilon)\}\), where \(\epsilon\) denotes the empty string. In other words, YES-instances of problems in P do not need a certificate and we can decide membership in polynomial time with \(x\) alone.
A problem in NP: \(\{x : \exists y \text{ with } |y| \leq |x|^{O(1)}, B(x,y)\}\). In other words, YES-instances have some polynomial-length certificate \(y\).
A problem in coNP: \(\{x : \forall y \text{ with } |y| \leq |x|^{O(1)}, B(x,y)\}\). In other words, YES-instances require all possible polynomial-length certificates to satisfy \(B\).
Intuitively, problems in NP ask whether there
exists a string satisfying certain properties, whereas problems
in coNP ask whether all strings satisfy
certain properties. This comes from \(\neg
(\exists x: p(x)) \equiv \forall x: \neg p(x)\).
Let us consider the following example to further build intuition of the
relationship between NP and coNP. SAT
is a well-known problem in NP, which asks if a logical sentence \(S\) has a truth assignment which satisfies
it. Consider \(\neg S\). Verifying that
\(S\) is a tautology is equivalent to
checking that there is no valuation satisfying \(\neg S\). Consequently, TAUTOLOGY is the
complement of SAT but with a negated formula. Hence, TAUTOLOGY \(\in\) coNP.
We now introduce the following notation: \(\sum_{1}^{P} = \textbf{NP}\) and \(\Pi_{1}^{P} = \textbf{coNP}\).
The polynomial hierarchy (PH) contains \(\sum_{k}^{P}\) and \(\Pi_{k}^{P}\) for \(k \geq 1\) and is defined recursively as:
\[\begin{align*}
\sum_{k+1}^{P} := \exists^P\Pi_{k}^{P}
\\ \Pi_{k+1}^{P} := \forall^P\sum_{k}^{P}
\end{align*}\] The classes of the polynomial hierarchy can be
interpreted in the context of games, where languages in \(\Sigma_i\) ask if there exists a winning
strategy for \(\frac{i}{2}\) rounds for
player 1. Conversely, languages in \(\Pi_i\) can be interpreted as asking about
winning strategies for the second player.
If a PH-complete language exists, then there exists an \(i\) such that the polynomial hierarchy
collapses to the \(i\)th level.