Computational Complexity: A Conceptual Perspective (Draft)

Computational Complexity: A Conceptual Perspective (Draft)

Focuses on the high level study of computation, exploring the connections among computational problems and notions. Covers theory of NP-completeness, approximation, probabilistic proof systems, pseudorandomness and cryptography.

Publication date: 28 Apr 2008

ISBN-10: 052188473X

ISBN-13: 9780521884730

Paperback: 632 pages

Views: 19,809

Type: Book

Publisher: Cambridge University Press

License: n/a

Post time: 27 Oct 2006 06:00:11

Computational Complexity: A Conceptual Perspective (Draft)

Computational Complexity: A Conceptual Perspective (Draft) Focuses on the high level study of computation, exploring the connections among computational problems and notions. Covers theory of NP-completeness, approximation, probabilistic proof systems, pseudorandomness and cryptography.
Tag(s): Theory of Computation
Publication date: 28 Apr 2008
ISBN-10: 052188473X
ISBN-13: 9780521884730
Paperback: 632 pages
Views: 19,809
Document Type: Book
Publisher: Cambridge University Press
License: n/a
Post time: 27 Oct 2006 06:00:11
Terms and Conditions:
Oded Goldreich wrote:Permission to make copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Abstracting with credit is permitted.

Book Excerpts:

The (half-century) history of Complexity Theory has witnessed two main research efforts (or directions). The first direction is aimed towards actually establishing concrete lower bounds on the complexity of problems, via an analysis of the evolution of the process of computation. Thus, in a sense, the heart of this direction is a "low-level" analysis of computation. Most research in circuit complexity and in proof complexity falls within this category. In contrast, a second research effort is aimed at exploring the connections among computational problems and notions, without being able to provide absolute statements regarding the individual problems or notions. This effort may be viewed as a "high-level" study of computation. The theory of NP-completeness as well as the studies of approximation, probabilistic proof systems, pseudorandomness and cryptography all fall within this category.

The current book focuses on the latter effort (or direction). There are several reasons for the decision to focus on the "high-level" direction. The first is the great conceptual significance of the known results; that is, many known results (as well as open problems) in this direction have an appealing conceptual message, which can also be appreciated by non-experts. Furthermore, these conceptual aspects may be explained without entering into excessive technical detail. Consequently, the "high-level" direction is more suitable for an exposition in a book of the current nature.

Intended Audience:

This book offers a conceptual perspective on complexity theory, and the presentation is designed to highlight this perspective. It is intended mainly for students that wish to learn complexity theory and for educators that intend to teach a course on complexity theory. The book is also intended to promote interest in complexity theory and make it acccessible to general readers with adequate background (which is mainly being comfortable with abstract discussions, definitions and proofs). Most readers are expected to have a basic knowledge of algorithms, or at least be fairly comfortable with the notion of an algorithm.
 




About The Author(s)


No information is available for this author.

Oded Goldreich

No information is available for this author.


Book Categories
Sponsors