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 complete problems, whereas those that do not, don't have complete problems. For example, NP, co-NP, PLS, PPA all have complete problems, while RP, ZPP, BPP and TFNP do not have complete problems.