We're going to be looking at some examples of problems that are outside of $\mathbf{NP}$. In a sense, what we'll do is think about how to generalize the notion of nondeterminism, characterize some new classes, and consider some new problems.
Recall the problem $\text{MIN-FORMULA}$ that we briefly mentioned last class. Essentially, this is the problem of whether a given formula $\varphi$ is a minimal formula. That is, there is no smaller formula with the same set of satisfying assignments. This is known to be in $\mathbf{PSPACE}$ but is not known to be $\mathbf{PSPACE}$-complete.
Another similar problem is $\text{EXACT-VC}$: Given a graph $G$ and an integer $k$, is the smallest vertex cover of $G$ of size $k$? Here, we are asking for two things: that $G$ contains a vertex cover of size $k$ and that every other vertex cover has size at least $k$.
We define some new classes to capture the notion of what we want to express with these two problems.
The class $\Sigma_2^P$ is the set of all languages $L$ for which there exists a polynomial time verifier $M$ and polynomial $n^k$ such that $$ w \in L \iff \exists u \in \Sigma^{n^k} \forall v \in \Sigma^{n^k} \text{$M$ accepts $\langle w, u, v \rangle$}.$$
We can see from this definition that we $\text{EXACT-VC}$ and $\text{MIN-FORMULA}$ are in $\Sigma_2^P$, by how we phrase what the problems are looking for.
We can define a similar class: $\Pi_2^P = \{ \overline L \mid L \in \Sigma_2^P\}$. Alternatively, we have $$ w \in L \iff \forall u \in \Sigma^{n^k} \exists v \in \Sigma^{n^k} \text{$M$ accepts $\langle w, u, v \rangle$}.$$ Of course, we can see the analogy here to $\mathbf{NP}$ and $\mathbf{coNP}$. And if we can do it with those classes, then there's no reason we can't extend this to its natural conclusion.
The polynomial hierarchy is defined as follows. For every $i \geq 1$, a language $L$ is in $\Sigma_i^P$ if there exists a polynomial time TM $M$ and polnyomial $n^k$ such that $$ w \in L \iff \exists u_1 \in \Sigma^{n^k} \forall u_2 \in \Sigma^{n^k} \cdots Q_i u_i \in \Sigma^{n^k} \text{$M$ accepts $\langle w, u_1, u_2, \dots, u_i \rangle$}$$ where $Q_i$ is $\forall$ or $\exists$ depending on whether $i$ is even or odd.
A language $L$ is in $\Pi_i^P$ if there exists a polynomial time TM $M$ and polnyomial $n^k$ such that $$ w \in L \iff \forall u_1 \in \Sigma^{n^k} \exists u_2 \in \Sigma^{n^k} \cdots Q_i u_i \in \Sigma^{n^k} \text{$M$ accepts $\langle w, u_1, u_2, \dots, u_i \rangle$}$$ where $Q_i$ is $\exists$ or $\forall$ depending on whether $i$ is even or odd.
The polynomial hierarchy is $\mathbf{PH} = \bigcup_i \Sigma_i^P$.
Note that by this definition, we have $\Sigma_1^P = \mathbf{NP}$, $\Pi_1^P = \mathbf{coNP}$, and $\Sigma_0^P = \Pi_0^P = \mathbf P$. We also have $\Pi_i^P = \mathbf{co}\Sigma^P_i$ and $\Sigma_i^P \subseteq \Pi_{i+1}^P$.
Of course, this definition is reliant on the fact that $\mathbf P \neq \mathbf{NP}$. Currently, we don't know whether any of these inclusions are strict inclusions. There is also the possibility that these inclusions are strict, up to a point. If there's some $i$ for which the inclusions are no longer strict, we say the polynomial hierarchy collapses to level $i$. That is, there would exist some $i$ such that $\Sigma_i^P = \bigcup_j \Pi_j^P = \mathbf{PH}$.
Theorem. For every $i \geq 1$, if $\Sigma_i^P = \Pi_i^P$, then $\mathbf{PH} = \Sigma_i^P$.
Proof. Fix $k$ and assume $\Sigma_k^P = \Pi_k^P$. It's clear that for all $i \leq k$, we have $\Sigma_i^P, \Pi_i^P \subseteq \Sigma_k^P$. Thus, we just need to show that for every $i \geq k$, we have $\Sigma_i^P, \Pi_i^P \subseteq \Sigma_k^P$. We will show this by showing that $\Sigma_i^P = \Sigma_{i-1}^P$ for $i > k$.
Let $L \in \Sigma_i^P$. We will label our quantifiers in reverse to make things easier to read. By definition, there is a polynomial time TM $M$ such that $$ w \in L \iff \exists u_i \forall u_{i-1} \cdots Q_1 u_1 \text{$M$ accepts $\langle w, u_i, u_{i-1}, \dots, u_1 \rangle$}.$$ Now, define a language $L'$ such that $$ \langle w,u_i,\dots,u_{k+1} \rangle \in L' \iff \exists u_k \cdots Q_1 u_1 \text{$M$ accepts $\langle w, u_i, \dots, u_1 \rangle$}.$$ Here, we assumed that $u_k$ happens to be quantified existentially, but it's not difficult to see that we can apply a similar argument if $i$ and $k$ happened to work out differently. By this definition, we have $L' \in \Sigma_k^P$ but by the assumption in the statement of the theorem, we also have $L' \in \Pi_k^P$. Then this means that there is a polynomial time Turing machine $M'$ that decides $L'$ such that $$ \langle w,u_i,\dots, u_{k+1} \rangle \in L' \iff \forall v_k \cdots Q'_1 v_1 \text{$M'$ accepts $\langle w, u_i, \dots u_{k+1}, v_k, \dots, v_1 \rangle$}.$$ This definition then gives us the following \begin{align} w \in L & \iff \exists u_i \forall u_{i-1} \cdots \forall u_{k+1} u_{k+1} \langle w, u_i, \dots, u_{k+1} \rangle \in L' \\ & \iff \exists u_i \forall u_{i-1} \cdots \forall u_{k+1} [\forall v_k \cdots Q_1'v_1 \text{$M'$ accepts $\langle w,u_i,\dots,v_1 \rangle$}] \\ & \iff \exists u_i \forall u_{i-1} \cdots \forall u_{k+1} v_k \exists v_{k-1} \cdots Q_1' v_1 \text{$M'$ accepts $\langle w,u_i,\dots,v_1 \rangle$}. \end{align} Note that the final expression only has $i-1$ quantifiers. Thus, $L \in \Sigma_{i-1}$. $$\tag*{$\Box$}$$
Theorem. If $\mathbf P = \mathbf{NP}$, then $\mathbf{PH} = \mathbf P$.
Proof. Left as an exercise for the reader. $$\tag*{$\Box$}$$
Now, we can show that for every $i$, there exist problems that are $\Sigma_i^P$ and $\Pi_i^P$-complete. For each $i \geq 1$, we define the following $\Sigma_i^P$-complete problem $$\Sigma_i\mathrm{SAT} = \exists u_1 \forall u_2 \exists u_3 \cdots Q_i u_i \varphi(u_1,\dots,u_i) = 1.$$ This is a special case of $\mathrm{TQBF}$. We can define a similar problem $\Pi_i \mathrm{SAT}$ that is $\Pi_i^P$-complete.
However, we do not know of any $\mathbf{PH}$-complete problem, since that would show $\mathbf{PH} = \Sigma_i^P$ for some $i$. Similarly, we have $\mathbf{PH} \subseteq \mathbf{PSPACE}$, but we do not know if $\mathbf{PH} = \mathbf{PSPACE}$. However, one implication of $\mathbf{PH}$ not having a complete problem is that $\mathbf{PH} \neq \mathbf{PSPACE}$.
An alternate characterization of the classes of the polynomial hierarchy is given by a special type of Turing machine called an alternating Turing machine.
An alternating Turing machine is a nondeterministic Turing machine with an additoinal feature. Its states, except for $q_A$ and $q_R$ are divided into universal and existential states. When we run an ATM on an input string, we label each node of its nondeterministic computation tree with $\wedge$ or $\vee$, depending on whether the corresponding configuration contains a universal or existential state. We designate a node to be accepting if it is label with $\wedge$ and all of its children are accepting, or if it is labeled with $\vee$ and any of its children are accepting. The input is accepted if the start node is designated accepting.
We have the following characterization. Let $\mathbf{ATIME}(n)$ be the class of languages that are decidable on an alternating Turing machine in time $f(n)$. We define $\mathbf{AP} = \bigcup_k \mathbf{ATIME}(n^k)$. For each $i \in \mathbb N$, we can define $\Sigma_i \mathbf{TIME}(f(n))$ to be the set of languages decidable by a $f(n)$ time ATM $M$ with an initial state labeled $\exists$ and alternates at most $i-1$ times. We can define $\Pi_i \mathbf{TIME}(f(n))$ similarly.
Theorem. For every $i \in \mathbb N$, $\Sigma_i^P = \bigcup_k \Sigma_i\mathbf{TIME}(n^k)$ and $\Pi_i^P = \bigcup_k \Pi_i \mathbf{TIME}(n^k)$.
However, if we allow an unlimited number of alternations, we get the following result.
Theorem. $\mathbf{AP} = \mathbf{PSPACE}$.
Another common characterization of the classes of the polynomial hierarchy is given by oracle machines.
Theorem. For every $i \geq 2$, $\Sigma_i^P = \mathbf{NP}^{\Sigma_{i-1}\mathrm{SAT}}$ and $\Pi_i^P = \mathbf{coNP}^{\Sigma_{i-1}\mathrm{SAT}}$.
These classes are also often denoted by $\Sigma_i^P = \mathbf{NP}^{\Sigma_{i-1}^P}$ and $\Pi_i^P = \mathbf{coNP}^{\Sigma_{i-1}^P}$.