complexity class

(redirected from Complexity classes)
Also found in: Wikipedia.

complexity class

(algorithm)
A collection of algorithms or computable functions with the same complexity.
References in periodicals archive ?
They have strong consequences concerning separation of complexity classes, but only a few special cases have been proved.
He has also made several notable contributions to computer science outside of cryptography, such as finding the first linear time algorithm for 2-satisfiability and showing the equivalence of the complexity classes PSPACE and IP.
His topics are basic ideas of classical and quantum computational models and complexity classes, mathematical tools and simple quantum mechanics required for quantum computing, quantum gates and quantum circuits, quantum algorithms, quantum error correction, quantum teleportation and superdense coding, and quantum cryptography.
Complexity classes for one-variable complexity functions, such as [THETA](g(n)), O(g(n)), [OMEGA](g(n)), o(g(n)), [omega](g(n)) are presented in almost every material that includes elements of the theory of complexity; see, for example, (Knuth, 1997), (Cormen et al.
In this paper we define five new complexity classes for multi-variable complexity functions and we prove some properties of these new defined classes.
In Section 2, we remind the definitions of the complexity classes for one-variable complexity functions and we give the definitions for five new complexity classes for multi-variable complexity functions.
Definition 1: Consider the following complexity classes for one-variable complexity functions (Cormen et al.
Definition 3: Next, we define five new complexity classes for multi-variable complexity functions:
SOME PROPERTIES OF THE COMPLEXITY CLASSES FOR MULTI-VARIABLE FUNCTIONS
In this paper we give the definitions to five new complexity classes for multi-variable complexity functions and we prove several properties related to these complexity classes.
This will allow for comparison of complexity classes defined from different computational paradigms (e.