Computational complexity

by Oded Goldreich

2008 500 pages eng

Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural comput…