complexity class


Also found in: Wikipedia.

complexity class

(algorithm)
A collection of algorithms or computable functions with the same complexity.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
Each complexity class had unique demographic profiles (Table 2).
The proposed methods can be recommended for similar studies of fourth and higher complexity class mechanisms when closed notion path (contours).
Plexus is a leader in manufacturing mid-to-low volume, higher complexity Class II and Class III medical products.
It can be observed that these classes make the link between the complexity of an algorithm, expressed as a multi-variable complexity function (see, for example f([n.sub.1], [n.sub.2], ..., [n.sub.k])), and a complexity class, based on a one-variable complexity function (see, for example [bar.O] (g(n))).
To classify computations (or problems) we introduced the key concept of a complexity class in terms of the Turing machines with bounded computational resources.
In almost every case, we show that the decision problem is complete for some known complexity class. Some of these results are familiar from work by Papadimitriou and Tsitsiklis and others, but some, such as our PL-completeness proofs, are surprising.