Arora - Computational Complexity - A Modern Approach (Cambridge, 2009).pdf

(4671 KB) Pobierz

This page intentionally left blank

COMPUTATIONAL COMPLEXITY

This beginning graduate textbook describes both recent achievements and

classical results of computational complexity theory. Requiring essentially

no background apart from mathematical maturity, the book can be used

as a reference for self-study for anyone interested in complexity, including

physicists, mathematicians, and other scientists, as well as a textbook for

a variety of courses and seminars. More than 300 exercises are included

with a selected hint set.

The book starts with a broad introduction to the ﬁeld and progresses

to advanced results. Contents include deﬁnition of Turing machines and

basic time and space complexity classes, probabilistic algorithms, inter-

active proofs, cryptography, quantum computation, lower bounds for

concrete computational models (decision trees, communication complex-

ity, constant depth, algebraic and monotone circuits, proof complexity),

average-case complexity and hardness ampliﬁcation, derandomization and

pseudorandom constructions, and the PCP Theorem.

Sanjeev Arora is a professor in the department of computer science at

Princeton University. He has done foundational work on probabilistically

checkable proofs and approximability of

NP-hard

problems. He is the

founding director of the Center for Computational Intractability, which is

funded by the National Science Foundation.

Boaz Barak is an assistant professor in the department of computer science

at Princeton University. He has done foundational work in computational

complexity and cryptography, especially in developing “non-blackbox”

techniques.

COMPUTATIONAL

COMPLEXITY

A Modern Approach

SANJEEV ARORA

Princeton University

BOAZ BARAK

Princeton University