# Time and Space Complexity Class

Robust classes are those such that no reasonable changes to the model of computation should
change the class; capable of classifying interesting problems. Examples

• $$\mathsf{L}$$ (contains Formula Value, integer multiplication and division),
• $$\mathsf{P}$$ (contains circuit value, linear programming, max flow),
• $$\mathsf{PSPACE}$$ (contains 2-person games),
• $$\mathsf{EXP}$$ (contains all of PSPACE).

A complexity class is a collection of languages decidable by a computation model within a resource bound. Complexity classes are usually specified by

• computation model: TM, boolean circuit, RAM, PRAM
• computation mode: deterministic, non-deterministic, oracle, randomization
• resources: time, space,
• bound: $$f(|x|)$$.

A proper complexity function should be computable in $$O(n+f(n))$$ time and $$O(f(n))$$ space.
For a proper function $$f \colon N \to N$$,

• $$\mathsf{TIME}(f(n)) = \{L \mid L \hbox{ is decided by a TM running in time bound f(n) }\}$$
• $$\mathsf{SPACE}(f(n)) = \{L \mid L \hbox{ is decided by a TM running in space bound f(n) }\}$$

The complement of a language $$L$$ is $$\bar{L} = \Sigma^* -L$$. For any complexity class $$C$$, $$coC$$ is $$\{\bar{L} \mid L\in C \}$$. All deterministic time and space complexity classes are closed under complement. Non-deterministic space complexity classes are also closed under complement. However, nondeterministic time classes are unknown to be closed.

Relationships between time and space classes:
$\mathsf{TIME}(f(n)) \subseteq \mathsf{NTIME}(f(n)) \subseteq \mathsf{SPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n)) \subseteq \mathsf{TIME}(2^{O(f(n)+\mathsf{L}og n})$

To simulate a NTM $$N$$ with a TM $$M$$,

• $$N$$ runs in $$\mathsf{NTIME}(f(n))$$. $$M$$ can simulate each non-deterministic computation path one-by-one by reusing the space. Each computation path can access at most $$f(n)$$ space in time $$f(n)$$.
• $$N$$ runs in $$\mathsf{NSPACE}(f(n))$$. Each configuration of $$N$$ is specified by its state, head positions, and tape contents. The number of configurations is $$O(c n 2^{k f(n)}) = O(2^{O(f(n) + \mathsf{L}og n})$$. $$M$$ can simulate $$N$$ by running over the configuration graph in time $$O(2^{O(f(n) + \mathsf{L}og n})$$.

$\mathsf{NSPACE}(f(n)) \subseteq \mathsf{SPACE}(f^2(n))$ for $$f(n) \geq \mathsf{L}og n$$
$\mathsf{NSPACE}(f(n)) = \coNSPACE(f(n))$ for $$f(n) \geq \mathsf{L}og n$$

Savitch’s theorem $${Reachability} \in \mathsf{SPACE}(\mathsf{L}og^2 n)$$. The Immerman-Szelepscenyi theorem $${Reachability} \in \mathsf{coNL}$$

• $$\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXP}$$latex
• $$\mathsf{L} \nsubseteq \mathsf{PSPACE}$$ and $$\mathsf{P} \subsetneq \mathsf{EXP}$$.
• $$\mathsf{P}\subseteq \mathsf{coNP} \subseteq \mathsf{PSPACE}$$latex
• $$\mathsf{NL} = \mathsf{coNL}$$ $$\mathsf{PSPACE} = \mathsf{NPSPACE} = \mathsf{coNPSPACE}$$

$$\textsc{Reachability}$$ is in $$\mathsf{SPACE}(\mathsf{L}og^2 n)$$, $$\NL(\mathsf{coNL})-complete$$, $$\mathsf{TIME}(|N|^2)$$, $$\mathsf{TIME}(|E|)$$

Relationships between the classes:

• $$\mathsf{L} \subseteq \mathsf{P} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXP}$$.
To see $$\mathsf{P} \subseteq \mathsf{PSPACE}$$, a TM can access at most polynomial space in polynomial time. To show $$\mathsf{L} \subseteq \mathsf{P}$$ and $$\mathsf{PSPACE} \subseteq \mathsf{EXP}$$, we need the fact that the running time of a TM is at most the total number of all its possible configurations. In space $$f(n)$$, the number of configurations is $$g(n) = n \mathsf{TIME}s f(n)\mathsf{TIME}s |Q| \mathsf{TIME}s |\Sigma|^{f(n)}$$, taking into account of head positions of the input and work tapes, the number of states, and the work tape contents. It holds that $$g(n)\mathsf{L}eq e^{cf(n)}$$.

• $$\mathsf{L} \subsetneq \mathsf{PSPACE}$$ and $$\mathsf{P} \subsetneq \mathsf{EXP}$$.
With time and space hierarchy theorems, $$\mathsf{TIME}(n) \subsetneq \mathsf{TIME}(n \mathsf{L}og n)$$ and $$\mathsf{SPACE}(n) \subsetneq \mathsf{SPACE}(n \mathsf{L}og n)$$.
• $$\mathsf{L} \stackrel{?}{=} \mathsf{P}$$, $$\mathsf{P} \stackrel{?}{=} \mathsf{PSPACE}$$, $$\mathsf{PSPACE} \stackrel{?}{=} \mathsf{EXP}$$. At least one have a negative answer.

If $$\mathsf{L} = \mathsf{P}$$, then $$\mathsf{PSPACE} = \mathsf{EXP}$$.

[Padding technique] Suppose $$L \in \mathsf{EXP}$$ is decided by a TM $$M_0$$ in time $$2^{n^c}$$. We define $$L_{\#} = \{x\#^{2^{|x|^c}} \mid x\in L \}$$ by adding paddings.
Then we can easily modify $$M_0$$ to construct $$M_1$$ which can decide $$L_{\#}$$ in linear time. Note the input size for $$M_1$$ is $$m = n + 2^{n^c}$$, where $$n$$ is the input size for $$M_0$$. Thus $$L_\# \in \mathsf{P}$$, and with the assumption $$\mathsf{L}=\mathsf{P}$$, we have $$L_\# \in \mathsf{L}$$, which means $$L_\#$$ can be decided by some TM $$M_2$$ in logspace. Then we can modify $$M_2$$ to construct $$M_3$$ which can decide $$L$$ in space $$O(\mathsf{L}og(n + 2^{n^c})) = O(n^c)$$. This simply implies $$L \in \mathsf{PSPACE}$$.

In a nondeterministic Turing machine (NTM), the transition function is $$\delta \colon Q \mathsf{TIME} \Sigma \to 2^{Q\mathsf{TIME}s \Sigma \mathsf{TIME}s\{l,r,s\}}$$.

The language recognized by a NTM is $$L(N)$$ where $$x\in L(N)$$ iff there exists some accepting computation.

The time is the maximum length of the path. The space is the maximum work-tape space of any path.

$\mathsf{NTIME}(f(n))$ $$NSPACE(f(n))$$

• $$\mathsf{NP} = \cup_k \mathsf{NTIME}(n^k)$$
• $$\mathsf{NEXP} = \cup_k \mathsf{NTIME}(2^{n^k})$$
• $$\mathsf{NL} = \mathsf{NSPACE}(\mathsf{L}og n)$$
• $$\mathsf{NPSPACE} = \cup_k \mathsf{NSPACE}(n^k)$$

Reachability in directed graphs is in $$\mathsf{NL}$$, but reachability in undirected graphs is in $$\mathsf{L}$$.

$$\mathsf{NPSPACE} = \mathsf{PSPACE}$$

A verifier for a language $$L$$ is an algorithm $$V$$ such that
$L = \{x \mid V \hbox{ accepts } (x, c) \hbox{ for some string c}\}.$
We measure the time of a verifier only in terms of the length of $$x$$ so a \emph{polynomial time verifier} runs in polynomial time in the length of $$x$$. A language $$A$$ is \emph{polynomially verifiable} if it has a polynomial time verifier.

$$\mathsf{NP}$$ is the class of languages that have polynomial time verifiers.

$$L \in \mathsf{NP}$$ if there is a language $$R \in \mathsf{P}$$ and a constant $$c$$ such that $$L = \{x \mid \exists y ~ |y| < |x|^c ~ (x, y) \in R\}[/latex]. A huge number of real-life problems are in NP because they are of the form: problem description such that a solution to the problem is small and the solution is easy to test for correctness. • [latex]\mathsf{P} \subseteq \mathsf{NP}$$ and $$\mathsf{EXP} \subseteq \mathsf{NEXP}$$.
• $$\mathsf{NP} \subseteq \mathsf{PSPACE}$$.

Try all possible ways.

• $$\mathsf{P} \stackrel{?}{=} \mathsf{NP}$$.

Generating a solution vs. recognizing a solution.