*World of Computer Science*. ©2005-2006 Thomson Gale, a part of the Thomson Corporation. All rights reserved.

This section contains 458 words(approx. 2 pages at 300 words per page) |

Computational **Complexity Theory** is the discipline of recognising solvable problems that are intractable in the sense that no efficient algorithm exists to solve them. Problems that computational processes are intended to solve can be divided into "decision problems," "functions," and "relations." It is possible to reformulate both decision problems and relations functions, which means that effectively **computability** can be reduced to solving **function** problems.

A function is considered "computable" if there exists an algorithm for calculating the function that for any given legal combination of input values produces the correct result within a finite time.

In 1936, English mathematician **Alan Turing** published a paper called "On computable numbers, with an application to the Entscheidungsproblem [decision problem]." Turing proposed a simple abstract computing machine, based on a notional mathematician with a pencil, an eraser, and a **stack** of paper. Turing stated that any function is computable if it is computable...

This section contains 458 words(approx. 2 pages at 300 words per page) |