Complete (complexity)
From Wikipedia, the free encyclopedia
In computational complexity theory, a computational problem is complete for a complexity class when it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class. Complexity classes are sets of all of the problems that can possibly be solved with at most a certain amount of some computational resource, and may include problems that actually require far less resources. The complete problems, however, are the most resource-intensive problems in the class.
Besides being very resource-intensive, complete problems are very expressive; in some sense, they "encode" all of the expressiveness or difficulty of the complexity class. This is because, given a method of efficiently solving a complete problem, we can efficiently solve any other problem in the complexity class. So, for example, many of the problems in EXPTIME, the exponential time class, are very hard, and we could never hope to find efficient solutions for them. But if we were given a magic box that quickly solved any EXPTIME-complete problem (called an oracle machine for that problem), we could quickly solve any other problem in EXPTIME.
When a problem has the property that it allows you to quickly solve any problem in a complexity class, we say that it is hard for that class. Equivalently, we can say that there is a reduction from any problem in the class to the hard problem. When a problem is both hard for a class, and a member of the class, it is complete for that class.
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).
It is possible to define classes that can be proven to lack complete problems; for example, Sipser showed that there is a language M such that BPPM (BPP with oracle M) has no complete problems.[1]
[edit] References
- ^ 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.
