Complete (complexity): Difference between revisions
m →top: replaced: well-known → well known |
Citation bot (talk | contribs) m Removed URL that duplicated unique identifier. | You can use this bot yourself. Report bugs here.| Activated by User:Nemo bis | via #UCB_webform |
||
Line 11: | Line 11: | ||
Generally, complexity classes that have a recursive enumeration have known complete problems, whereas classes that lack a recursive enumeration have none. For example, [[NP (complexity)|NP]], [[co-NP]], [[PLS (complexity)|PLS]], [[PPA (complexity)|PPA]] all have known natural complete problems, while [[RP (complexity)|RP]], [[ZPP (complexity)|ZPP]], [[Bounded-error probabilistic polynomial|BPP]] and [[TFNP]] have no known complete problems (although such a problem may be discovered in the future).{{Citation needed|date=July 2008}} |
Generally, complexity classes that have a recursive enumeration have known complete problems, whereas classes that lack a recursive enumeration have none. For example, [[NP (complexity)|NP]], [[co-NP]], [[PLS (complexity)|PLS]], [[PPA (complexity)|PPA]] all have known natural complete problems, while [[RP (complexity)|RP]], [[ZPP (complexity)|ZPP]], [[Bounded-error probabilistic polynomial|BPP]] and [[TFNP]] have no known complete problems (although such a problem may be discovered in the future).{{Citation needed|date=July 2008}} |
||
There are classes without complete problems. For example, Sipser showed that there is a language '''M''' such that '''BPP'''<sup>'''M'''</sup> ('''BPP''' with [[oracle machine|oracle]] '''M''') has no complete problems.<ref>{{Cite book |
There are classes without complete problems. For example, Sipser showed that there is a language '''M''' such that '''BPP'''<sup>'''M'''</sup> ('''BPP''' with [[oracle machine|oracle]] '''M''') has no complete problems.<ref>{{Cite book | doi=10.1007/BFb0012797| chapter=On relativization and the existence of complete sets| title=Automata, Languages and Programming| volume=140| pages=523–531| series=Lecture Notes in Computer Science| year=1982| last1=Sipser| first1=Michael| isbn=978-3-540-11576-2}}</ref> |
||
== References == |
== References == |
Revision as of 08:20, 5 December 2019
This article needs additional citations for verification. (October 2008) |
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.
More formally, a problem p is called hard for a complexity class C under a given type of reduction if there exists a reduction (of the given type) from any problem in C to p. If a problem is both hard for the class and a member of the class, it is complete for that class (for that 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 classes that lack a recursive enumeration have none. For example, NP, co-NP, PLS, PPA all have known natural complete problems, while RP, ZPP, BPP and TFNP have no 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
- ^ Sipser, Michael (1982). "On relativization and the existence of complete sets". Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 140. pp. 523–531. doi:10.1007/BFb0012797. ISBN 978-3-540-11576-2.