 Complete (complexity)

In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class. If a problem has the property that it allows you to quickly solve any problem in a complexity class, it is called hard for that class.
More formally, a problem p is called hard for a complexity class C under a given type of reduction, if there is a reduction of this type from any problem in C to p. If a problem is both hard for a class, and a member of the class, it is complete for that class (under the given type of reduction).
A problem that is complete for a class C is said to be Ccomplete, and the class of all problems complete for C is denoted Ccomplete. The first complete class to be defined and the most wellknown is NPcomplete, a class that contains many difficulttosolve problems that arise in practice. Similarly, a problem hard for a class C is called Chard, e.g. NPhard.
Normally it is assumed that the reduction in question does not have higher computational complexity than the class itself. Therefore it may be said that if a Ccomplete problem has a "computationally easy" solution, then all problems in "C" have an "easy" solution.
Generally, complexity classes that have a recursive enumeration have known complete problems, whereas those that do not, don't have any known complete problems. For example, NP, coNP, PLS, PPA all have known natural complete problems, while RP, ZPP, BPP and TFNP do not have any known complete problems (although such a problem may be discovered in the future).^{[citation needed]}
There are classes without complete problems. For example, Sipser showed that there is a language M such that BPP^{M} (BPP with oracle M) has no complete problems.^{[1]}
References
 ^ M. Sipser. On relativization and the existence of complete sets, Proceedings of ICALP'82, SpringerVerlag Lecture Notes in Computer Science volume 140, pp. 523531, 1982.
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Complete — To be complete is to be in the state of requiring nothing else to be added. Complete may also refer to: Complete (Lila McCann album) Complete (News from Babel album) Complete (complexity), in mathematics Complete metric space, in mathematics… … Wikipedia
Complete (disambiguation) — To be complete is to be in the state of requiring nothing else to be added.Complete may also refer to:* Complete (album), a 2001 country album * Complete (box set), a 2006 avant progressive rock album * Complete (complexity), in mathematics *… … Wikipedia
Complete coloring — of the Clebsch graph with 8 colors. Every pair of colors appears on at least one edge. No complete coloring with more colors exists: in any 9 coloring some color would appear only at one vertex, and there would not be enough neighboring vertices… … Wikipedia
Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… … Wikipedia
Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… … Wikipedia
complexity — /keuhm plek si tee/, n., pl. complexities for 2. 1. the state or quality of being complex; intricacy: the complexity of urban life. 2. something complex: the complexities of foreign policy. [1715 25; COMPLEX + ITY] * * * ▪ scientific theory… … Universalium
Complexity — For other uses, see Complexity (disambiguation). In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In… … Wikipedia
Completelinkage clustering — In cluster analysis, complete linkage or farthest neighbour is a method of calculating distances between clusters in agglomerative hierarchical clustering. In complete linkage,[1] the distance between two clusters is computed as the maximum… … Wikipedia
complexity theory — noun : a field of study shared by mathematics and computer science that is concerned with how the computational complexity of problems increases as the number of cases involved increases and with the classification of the problems according to… … Useful english dictionary
Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… … Wikipedia