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...