complexity class

If $f(n)$ is any function and $T$ is a Turing machine (of any kind) which halts on all inputs, we say that $T$ is time bounded by $f(n)$ if for any input $x$ with length $|x|$, $T$ halts after at most $f(|x|)$ steps.

For a decision problem $L$ and a class $K$ of Turing machines, we say that $L\in KTIME(f(n))$ if there is a Turing machine $T\in K$ bounded by $f(n)$ which decides $L$. If $R$ is a search problem then $R\in KTIME(f(n))$ if $L(R)\in KTIME(f(n))$. The most common classes are all restricted to one read-only input tape and one output/work tape (and in some cases a one-way, read-only guess tape) and are defined as follows:

• $D$ is the class of deterministic Turing machines. (In this case $KTIME$ is written $DTIME$.)

• $N$ is the class of non-deterministic Turing machines (and so $KTIME$ is written $NTIME$).

• $R$ is the class of positive one-sided error Turing machines and $coR$ the class of negative one-sided error machines

• $BP$ is the class of two-sided error machines

• $P$ is the class of minimal error machines

• $ZP$ is the class of zero error machines

Although $KTIME(f(n))$ is a time complexity class for any $f(n)$, in actual use time complexity classes are usually the union of $KTIME(f(n))$ for many $f$. If $\mathrm{\Phi }$ is a class of functions then $KTIME(\mathrm{\Phi })={\bigcup }_{f\in \mathrm{\Phi }}KTIME(f(n))$. Most commonly this is used when $\mathrm{\Phi }=𝒪(f(n))$.

The most important time complexity classes are the polynomial classes:

$$K𝒫=\bigcup _{i\in \mathbb{N}}KTIME(n^i)$$

When $K=D$ this is called just $𝒫$, the class of problems decidable in polynomial time. One of the major outstanding problems in mathematics is the question of whether $𝒫=𝒩𝒫$.

We say a problem $\pi \in KSPACE(f(n))$ if there is a Turing machine $T\in K$ which solves $\pi$, always halts, and never uses more than $f(n)$ cells of its output/work tape. As above, if $\mathrm{\Phi }$ is a class of function then $KSPACE(\mathrm{\Phi })={\bigcup }_{f\in \mathrm{\Phi }}KSPACE(f(n))$

The most common space complexity classes are $Kℒ=KSPACE(𝒪(\log n))$. When $K=D$ this is just called $ℒ$.

If $𝒞$ is any complexity class then $\pi \in co𝒞$ if $\pi$ is a decision problem and $\overline{\pi }\in 𝒞$ or $\pi$ is a search problem and $L(\pi )\in co𝒞$. Of course, this coincides with the definition of $coR$ above. Clearly $co(co𝒞)=𝒞$.

Since a machine with a time complexity $f(n)$ cannot possibly use more than $f(n)$ cells, $KTIME(f(n))\subseteq KSPACE(f(n))$. If $K\subseteq K^{\prime }$ then $KTIME(f(n))\subseteq K^{\prime }TIME(f(n))$ and similarly for space.

The following are all trivial, following from the fact that some classes of machines accept and reject under stricter circumstances than others:

$$D\subseteq ZP=R\cap coR$$

$$R\cup coR\subseteq BP\cap N$$

$$BP\subseteq P$$

Title	complexity class
Canonical name	ComplexityClass
Date of creation	2013-03-22 13:01:59
Last modified on	2013-03-22 13:01:59
Owner	Henry (455)
Last modified by	Henry (455)
Numerical id	4
Author	Henry (455)
Entry type	Definition
Classification	msc 68Q15