Computational Complexity: A Quantitative Perspective - 1st Edition - ISBN: 9780444828415, 9780080476667

Computational Complexity: A Quantitative Perspective, Volume 196

1st Edition

Authors: Marius Zimand
Hardcover ISBN: 9780444828415
eBook ISBN: 9780080476667
Imprint: Elsevier Science
Published Date: 7th July 2004
Page Count: 352
Tax/VAT will be calculated at check-out
140.00
220.00
235.00
175.00
Unavailable
Compatible Not compatible
VitalSource PC, Mac, iPhone & iPad Amazon Kindle eReader
ePub & PDF Apple & PC desktop. Mobile devices (Apple & Android) Amazon Kindle eReader
Mobi Amazon Kindle eReader Anything else

Institutional Access


Table of Contents

Contents Preface.

  1. Preliminaries.

  2. Abstract complexity theory.

  3. P, NP, and E.

  4. Quantum computation.

  5. One-way functions, pseudo-random generators.

  6. Optimization problems.

A. Tail bounds.

Bibliography.

Index.


Description

Contents Preface.

  1. Preliminaries.

  2. Abstract complexity theory.

  3. P, NP, and E.

  4. Quantum computation.

  5. One-way functions, pseudo-random generators.

  6. Optimization problems.

A. Tail bounds.

Bibliography.

Index.

Key Features

· Emphasis is on relevant quantitative attributes of important results in complexity. · Coverage is self-contained and accessible to a wide audience. · Large range of important topics including: derandomization techniques, non-approximability of optimization problems, average-case complexity, quantum computation, one-way functions and pseudo-random generators, resource-bounded measure and topology.

Readership

University libraries, researchers in the field theory of computation, computational complexity, algorithms, and al graduate students in computer science.


Details

No. of pages:
352
Language:
English
Copyright:
© Elsevier Science 2004
Published:
Imprint:
Elsevier Science
eBook ISBN:
9780080476667
Hardcover ISBN:
9780444828415

Reviews

"This book analyzes quantitative aspects of some of the most important results in computational complexity. It will benefit most the reader who already knows the basic tenets of complexity and wants to find out more about it than what is covered in standard courses." --Gerhard Lischke


About the Authors

Marius Zimand Author

Affiliations and Expertise

Townson University, Townson, USA.