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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
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 MSC: 68Q15 (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)