The theory of NP-completeness has its roots in computability theory, which originated in the work of Turing, Church, Godel, and others in the 1930’s.
The class P is the class of decision problems solvable by some algorithm within a number of steps bounded by some fixed polynomial. NP stands for “nondeterministic polynomial time”, where NP is defined in terms of nondeterministic machines, machines that have more than one possible move from a given configuration.
The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time.
0 Responses to “Computational Complexity”