complexity class
<algorithm> A collection of algorithms or computable functions with the same complexity. (1996-04-24) | ||||
Search Dictionary:
Complexity class definition was found in categories: Encyclopedia(1)
Complexity class Definition from Encyclopedia Dictionaries & Glossaries
| Wikipedia English - The Free Encyclopedia |
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.
| See more at Wikipedia.org... |