Search

The Online Encyclopedia and Dictionary

 
     
 

Encyclopedia

Dictionary

Quotes

   
 

Complexity class

In computational complexity theory, a complexity class is a set of problems of related complexity. A typical complexity class has a definition of the form:

the set of problems that can be solved by abstract machine M using O(f(n)) of resource R (n is the size of the input)

For example, the class NP is the set of decision problems that can be solved by a non-deterministic Turing machine in polynomial time, while the class PSPACE is the set of decision problems that can be solved by a deterministic Turing machine in polynomial space . Some complexity classes are sets of function problems, such as FP.

Many complexity classes can be characterized in terms of the mathematical logic needed to express them; see descriptive complexity.

See also: List of complexity classes


Important complexity classes (more)
P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | L | NC | P-C
PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH



Last updated: 02-10-2005 21:30:15
Last updated: 05-03-2005 09:00:33