Up until now, we've been concerned with whether or not a problem is computationally solvable and we have lots of examples of useful problems that turned out to be computationally unsolvable. However, just because a problem is computationally solvable doesn't mean that we can necessarily solve it. The real challenge is whether a problem can be solved using a reasonable amount of resources. This additional constraint introduces the kinds of questions that complexity theory seeks to answer.
What kinds of resources are we talking about? The most common ones that we deal with are time and space. However, there are all sorts of other resources we can consider. We can consider the cost of querying a black box algorithm, the cost of acquiring random bits, or the cost of communication between multiple machines.
The goal of complexity theory is to be able to answer questions about how complex or difficult a problem is in terms of the resources that are required to compute it. We study this by examining the structure of various problems. Ultimately, we want to be able to talk about complexity and problems in a general sense, but like we did for computability theory, we need to fix a model of computation to start out and generalize later on.
We will be using the Turing machine as our standard model of computation. The Turing machine gives us a convenient way to talk about time and space. Namely, we can consider time in terms of the number of steps a Turing machine takes. This is useful because a TM step is a discrete unit and it always consists of the same actions: read, write, change state, and move the tape head. Similarly, the Turing machine has a natural concept of space, which we consider to be the number of tape cells that need to be used by the machine. Again, a tape cell is a discrete unit that is simple to count.
Let $M$ be a deterministic Turing machine that halts on all inputs. The running time or time complexity of $M$ is the function $T:\mathbb N \to \mathbb N$, where $T(n)$ is the maximum number of steps that $M$ uses on any input of length $n$. If $T(n)$ is the running time of $M$, we say that $M$ runs in time $T(n)$ and that $M$ is a $T(n)$ time Turing machine.
Let $f$ and $g$ be functions $f,g:\mathbb N \to \mathbb R$. We say $f(n) = O(g(n))$ if there exist $c$ and $n_0$ such that for all $n \geq n_0$, $f(n) \leq c\cdot g(n)$. We say that $g(n)$ is an upper bound for $f(n)$.
Let $T: \mathbb N \to \mathbb R$ be a function. The time complexity class $\mathbf{TIME}(T(n))$ is the collection of all languages that are decidable by an $O(T(n))$ time Turing machine.
Now that we have this notion of time based on the single tape deterministic Turing machine, it is worth asking whether the same properties apply to other models. We showed before that all of the augmentations that we made to the Turing machine didn't change its power. That is, a decidable or recognizable problem for one of the machines was also decidable or recognizable on the standard model. However, just because we can simulate a fancier machine doesn't mean that we can do so at no cost.
Theorem. Let $T(n)$ be a function, where $T(n) \geq n$. Then every $T(n)$ time multitape Turing machine has an equivalent $O(T^2(n))$ time single-tape Turing machine.
Proof. Let $M$ be a $k$-tape TM that runs in time $T(n)$. Then we construct $M'$ which has a single tape.
Recall how the single tape machine worked. We put all the tapes on one tape separated by $\#$ and with marked virtual tape heads. The machine makes two passes over the entire tape to check and update the tape heads on each simulation of a computation step on $M$.
How much time does this take? It depends on how much tape is used by the virtual tapes. Since $M$ ran in $T(n)$ time, each virtual tape has size at most $T(n)$. This gives us a total tape length of $O(T(n))$. Since each simulation step passes over the entire tape twice, we get $O(T(n))$ time for each simulation step.
Since we are simulating $M$, we will be simulating the $T(n)$ steps that $M$ takes. Each simluated step takes $O(T(n))$, giving us a total of $O(T^2(n))$ steps on $M'$. $$\tag*{$\Box$}$$
Let $N$ be a nondeterministic Turing machine that is a decider. The running time of $N$ is the function $T:\mathbb N \to \mathbb N$, where $T(n)$ is the maximum number of steps that $N$ uses on any branch of its computation on any input of length $n$.
Theorem. Let $T(n)$ be a function where $T(n) \geq n$. Then every $T(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{O(T(n)}$ time deterministic single-tape Turing machine.
Proof. Let $N$ be a nondeterministic TM running in $T(n)$ time. We construct $M$ that simluates $N$.
On an input of length $n$, each computation branch of $N$ has length at most $T(n)$. Every node in the tree has at most $k$ children, where $k$ is the maximum number of nondeterministic choices given by the transition function of $N$. This gives us at most $k^{T(n)}$ leaves.
Recall that we explore the tree breadth first. Since there are at most $k^{T(n)}$ leaves in the tree, there are a total of $O(k^{T(n)})$ nodes. Travelling to each node requires at most $O(T(n))$ steps. Then $M$ runs in $O(T(n)k^{T(n)}) = 2^{O(T(n))}$ time.
Since the machine that we built is a 3-tape machine, we apply the previous theorem to get a running time of $(2^{O(T(n))})^2 = 2^{O(2T(n))} = 2^{O(T(n))}$. $$\tag*{$\Box$}$$