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.

Comments

comments