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.