2 Computational Complexity
Stephan Mertens
Institut für Physik, Otto‐von‐Guericke Universität Magdeburg, Germany, Santa Fe Institute, USA
If the Theory of making Telescopes could at length be fully brought into Practice, yet there would be certain Bounds beyond which Telescopes could not perform.
Isaac Newton, Opticks
2.1 Basics
The branch of theoretical computer science known as computational complexity is concerned with classifying problems according to the computational resources required to solve them. Informally, a problem 
is computationally more complex than a problem
if the solution of
requires more resources than ...
Get Quantum Information, 2 Volume Set, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
