Computational complexity a quantitative perspective
There has been a common perception that computational complexity is a theory of "bad news" because its most typical results assert that various real-world and innocent-looking tasks are infeasible. In fact, "bad news" is a relative term, and, indeed, in some situations (e.g., in...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Amsterdam
Elsevier
2004, 2004
|
| Edition: | 1st ed |
| Series: | North-Holland mathematics studies
|
| Subjects: | |
| Online Access: | |
| Collection: | Elsevier eBook collection Mathematics - Collection details see MPG.ReNa |
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
- Includes bibliographical references (pages 321-332) and index