When we introduced the class $\mathbf{NP}$, it was mentioned that while a language in $\mathbf{NP}$ could be verified in polynomial time using a polynomial length certificate, the same could not be said if we wanted to show the inverse. For instance, it's very easy to check that a formula $\varphi$ is satisfiable via some assignment that I provide, but it is not clear how to do the same to show that $\varphi$ doesn't contain a satisfying assignment.
Just as we did with the class of efficiently verifiable decision problems, we can classify the class of problems which are the complements of efficiently verifiable decision problems.
We define the class $\mathbf{coNP}$ to be $$ \mathbf{coNP} = \{ L \mid \overline L \in \mathbf{NP} \}.$$ It's important to note that $\mathbf{coNP}$ is not $\overline{\mathbf{NP}}$. To make this more clear, we can define $\mathbf{coNP}$ in a different way.
We say that $L \in \mathbf{coNP}$ if there exists a polynomial time verifier $V$ that runs in time $n^k$ such that for every input string $w$, we have $w \in L$ if and only if $M$ accepts $\langle w,c \rangle$ for every string $c$ of length $n^k$.
We can define $\mathbf{coNP}$-completeness in the same way as $\mathbf{NP}$-completeness:a language is $\mathbf{coNP}$-complete if it is in $\mathbf{coNP}$ and every other language in $\mathbf{coNP}$ is polynomial time reducible to it.
Some obvious problems that are in $\mathbf{coNP}$ can be found just by taking a problem in $\mathbf{NP}$ and taking its complement (for example, $\overline{\mathrm{SAT}}$, the problem of whether a given formula $\varphi$ is not satisfiable). However, $\mathbf{coNP}$ does contain natural problems. We consider the problem $\text{TAUTOLOGY}$: Given a boolean formula $\varphi$, is $\varphi$ satisfied by every assignment?
Theorem. $\text{TAUTOLOGY}$ is $\mathbf{coNP}$-complete.
Proof. By definition, it is fairly clear that $\text{TAUTOLOGY} \in \mathbf{coNP}$. To show that every $L \in \mathbf{coNP}$ reduces to $\text{TAUTOLOGY}$, modify the Cook-Levin reduction from $\overline L$ to $\mathrm{SAT}$, since $\overline L \in \mathbf{NP}$. For every input word $w$, the reduction constructs a formula $\varphi_w$ which is satisfiable if and only if $w \in \overline L$. Then $\overline{\varphi_w} \in \mathrm{TAUTOLOGY}$ iff $w \in L$. $$\tag*{$\Box$}$$
It turns out that $\mathbf{NP}$ and $\mathbf{coNP}$ have a non-empty intersection: we have $\mathbf P \subseteq \mathbf{NP} \cap \mathbf{coNP}$. This isn't too difficult to see, since solving a problem in $\mathbf P$ gives us a way to verify the inverse problem.
However, like the $\mathbf P$ and $\mathbf{NP}$ question, we have an intuitive understanding of the difference between $\mathbf{NP}$ and $\mathbf{coNP}$ that breaks down when we try to determine the exact relation that these two classes have. It turns out we don't know whether $\mathbf{NP}$ and $\mathbf{coNP}$ are the same or different classes.
We can define the space complexity of a Turing machine in a similar way as the time complexity.
Let $M$ be a deterministic Turing machine that halts on all inputs. The space complexity of $M$ is the function $f : \mathbb N \to \mathbb N$, where $f(n)$ is the maximum number of tape cells that $M$ scans on any input of length $n$. If the space complexity of $M$ is $f(n)$, we say that it runs in space $f(n)$
If $M$ is nondeterministic, we define its space complexity $f(n)$ to be the maximum number of tape cells that $M$ scans on ay branch of its computation for any input of length $n$.
Let $f : \mathbb N \to \mathbb R$. We define the space complexity classes $$\mathbf{SPACE}(f(n)) = \{ L \mid \text{$L$ is decided by an $O(f(n))$ space DTM} \},$$ $$\mathbf{NSPACE}(f(n)) = \{ L \mid \text{$L$ is decided by an $O(f(n))$ space NTM} \}.$$
We've shown that $\mathrm{SAT}$ can be considered a "hard" problem because we don't know of an efficient (polynomial-time) algorithm that solves it. Here, we show that we can solve $\mathrm{SAT}$ in linear space.
Here, we see that we can just cycle through every assignment using the same portion of the tape. Since we have $m \leq n$ variables, this algorithm runs in $O(n)$ space.
This also shows us that space is possibly more powerful than time by demonstrating a property of space that seems fairly obvious: space can be reused, but time can't.
Now, we consider a nondeterministic algorithm for $ALL_{NFA}$. Recall that $ALL_{NFA}$ is the problem: Given an NFA $A$, does it accept every string? We give an algorithm for the complement $\overline{ALL_{NFA}}$. This language is not known to be in $\mathbf{NP}$ or $\mathbf{coNP}$.
We nondeterministically guess a string, run it on the NFA, and keep track of all the states it can be in.
We can restrict the search to words of length $2^n$, since if some longer string is rejected, the state markers would repeat and the section of the string that's repeated can be removed to get a shorter string.
Since we only need to keep track of the markers and the counter for the loop, the algorithm runs in nondeterministic space $O(n)$.
We define the class $\mathbf{PSPACE}$ to be the class of languages that are decidable in polynomial space on a determininstic Turing machine. That is, $$ \mathbf{PSPACE} = \bigcup_{k \geq 1} \mathbf{SPACE}(n^k).$$
We define the class $\mathbf{NPSPACE}$ to be the class of languages that are decidable in polynomial space on a nondetermininstic Turing machine. That is, $$ \mathbf{NPSPACE} = \bigcup_{k \geq 1} \mathbf{NSPACE}(n^k).$$
What do we know about $\mathbf{PSPACE}$? Clearly, $\mathbf{PSPACE} \subseteq \mathbf{NPSPACE}$. And since we can't read more than one tape cell per time step, we have $\mathbf P \subseteq \mathbf{PSPACE}$ and $\mathbf{NP} \subseteq \mathbf{NPSPACE}$. Furthermore, our $\mathrm{SAT}$ example earlier shows us a way to solve problems in $\mathbf{NP}$ in $\mathbf{PSPACE}$: by cycling through every certificate on the same amount of space. This gives us $\mathbf{NP} \subseteq \mathbf{PSPACE}$ and $\mathbf{coNP} \subseteq \mathbf{PSPACE}$.
We can also get a time bound on a language in $\mathbf{PSPACE}$. Recall that an LBA is bounded by the amount of space it can use, which gave us the number of distinct configurations an LBA can have. We can derive a similar bound for a polynomial space Turing machine. If a TM runs in $f(n)$ space, then it has at most $f(n) \cdot 2^{O(f(n))}$ configurations. Then such a machine must run in $f(n) \cdot 2^{O(f(n))}$ time, which gives us $\mathbf{PSPACE} \subseteq \mathbf{EXPTIME} = \bigcup_{k \geq 0} \mathbf{TIME}(2^{n^k})$.
This gives us the following picture: $$ \mathbf P \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE} \subseteq \mathbf{NPSPACE} \subseteq \mathbf{EXPTIME}.$$ It is important to note that we do not know if any of these are equal, except for $\mathbf P \neq \mathbf{EXPTIME}$, which we will prove later in the course, and $\mathbf{PSPACE} = \mathbf{NPSPACE}$, which we will now prove.