Computability and Complexity
From
(Difference between revisions)
| Line 1: | Line 1: | ||
| - | + | == Complexity theory == | |
| + | |||
| + | 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. | ||
| + | |||
| + | == Computability theory == | ||
| + | |||
| + | Part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. Computability theory addresses four main questions: | ||
| + | |||
| + | *What problems can Turing machines solve? | ||
| + | *What other systems are equivalent to Turing machines? | ||
| + | *What problems require more powerful machines? | ||
| + | *What problems can be solved by less powerful machines? | ||
Revision as of 14:39, 27 March 2009
Complexity theory
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.
Computability theory
Part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. Computability theory addresses four main questions:
- What problems can Turing machines solve?
- What other systems are equivalent to Turing machines?
- What problems require more powerful machines?
- What problems can be solved by less powerful machines?
