User:Tcshasaposse/Computational complexity theory
From Wikipedia, the free encyclopedia
Computational complexity theory, as a branch of the theory of computation in computer science, investigates the amount of resources (such as time, memory, randomness) required by algorithms for solving various computational problems.
The origins of computational complexity can be traced back to the early 1970s when it was realized that certain simple problems would take an inordinate amount of time to solve on any computer, even though these problems are in principle solvable. Moreover, the inherent difficulty of these problems does not have anything to do with the computing technology that was available in the 1970s. It appears that nature imposes intrinsic obstacles at performing certain computations, and a central question in complexity theory is to understand why and how these obstacles arise.