Complete (complexity)


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 C-complete, and the class of all problems complete for C is denoted C-complete. The first complete class to be defined and the most well-known is NP-complete, a class that contains many difficult-to-solve problems that arise in practice. Similarly, a problem hard for a class C is called C-hard, e.g. NP-hard.

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 C-complete 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, co-NP, 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 BPPM (BPP with oracle M) has no complete problems.[1]

References

  1. ^ M. Sipser. On relativization and the existence of complete sets, Proceedings of ICALP'82, Springer-Verlag Lecture Notes in Computer Science volume 140, pp. 523-531, 1982.

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

  • Complete-linkage 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