PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
complexity class (Definition)

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 $ \vert x\vert$, $ T$ halts after at most $ f(\vert x\vert)$ 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:

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 $ \Phi$ is a class of functions then $ KTIME(\Phi)=\bigcup_{f\in\Phi} KTIME(f(n))$. Most commonly this is used when $ \Phi=\mathcal{O}(f(n))$.

The most important time complexity classes are the polynomial classes:

$\displaystyle K\mathcal{P}=\bigcup_{i\in\mathbb{N}} KTIME(n^i)$

When $ K=D$ this is called just $ \mathcal{P}$, the class of problems decidable in polynomial time. One of the major outstanding problems in mathematics is the question of whether $ \mathcal{P}=\mathcal{NP}$.

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 $ \Phi$ is a class of function then $ KSPACE(\Phi)=\bigcup_{f\in\Phi} KSPACE(f(n))$

The most common space complexity classes are $ K\mathcal{L}=KSPACE(\mathcal{O}(\log n))$. When $ K=D$ this is just called $ \mathcal{L}$.

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

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:

$\displaystyle D\subseteq ZP=R\cap coR$
$\displaystyle R\cup coR\subseteq BP\cap N$
$\displaystyle BP \subseteq P$



"complexity class" is owned by Henry.
(view preamble)

View style:

Log in to rate this entry.
(view current ratings)

Cross-references: machine, complexity classes, cells, polynomial time, polynomial, union, time complexity, minimal error, two-sided error, machines, negative, one-sided error, positive, non-deterministic Turing machines, deterministic Turing machines, one-way, restricted, search problem, decides, class, decision problem, length, bounded, Turing machine, function
There is 1 reference to this entry.

This is version 1 of complexity class, born on 2002-09-06.
Object id is 3433, canonical name is ComplexityClass.
Accessed 3156 times total.

Classification:
AMS MSC68Q15 (Computer science :: Theory of computing :: Complexity classes )

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)