home | alphabetical index | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Computational complexity theoryComplexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps does it take to solve a problem) and space (how much memory does it take to solve a problem). Other resources can also be considered, such as how many parallel processors are needed to solve a problem in parallel. Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.## OverviewA single "problem" is an entire set of related questions, where each question is a finite-length string. For example, the problemFACTORIZE is: given an integer written in binary, return all of the prime factors of that number. A particular question is called an instance. For example, "give the factors of the number 15" is one instance of the FACTORIZE problem.
The
## Decision problems
Much of complexity theory deals with decision problems. A decision problem is a problem where the answer is always YES/NO. For example, the problem
Decision problems are often considered because an arbitrary problem can always be reduced to a decision problem. For example, the problem
Complexity theory often makes a distinction between YES answers and NO answers.
For example, the set NP is defined as the set of problems where the YES instances can be checked quickly. The set Co-NP is the set of problems where the NO instances can be checked quickly. The "Co" in the name stands for "complement". The ## The PNP questionThe set P is the set of decision problems that can be solved by a deterministic machine in polynomial time. The set NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. The question of whether P is the same set as NP is the most important open question in theoretical computer science. There is even a $1,000,000 prize for solving it. (See Complexity classes P and NP and oracles).
Questions like this motivate the concepts of ## Famous complexity classesThe following are some of the classes of problems considered in complexity theory, along with rough definitions. See computation for a chart showing which classes are subsets of other classes.
Many of these classes have a \'Co' partner (ie NP and Co-NP) which consists of the complements of all languages in the original class. For example if
If you don't see a class listed (such as
## Notable Researchers | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

copyright © 2004 FactsAbout.com |