| Description |
1 online resource (xiv, 87 pages) |
| Series |
Lecture notes in computer science ; 1001 |
|
Lecture notes in computer science ; 1001.
|
| Contents |
1. Introduction -- 2. On the resilience of polynomials -- 3. Low-degree tests -- 4. Transparent proofs and the class PCP -- 5. Hardness of approximations -- 6. Conclusions -- A. The Berlekamp Welch decoder -- B. Composing proof systems -- C.A characterization of NP via polynomial sequences |
| Summary |
This work is a fascinating piece of research in computer science: it is built on and combines deep theoretical results from various areas and, at the same time, takes into account applications to hard problems in several fields. The author provides important new foundational insights and essentially advances applicable techniques in such different areas as computational complexity, efficient (randomized) checking of proofs, programs and polynomials, approximation algorithms, NP-complete optimization, and error-detection and error-correction algorithms in coding theory |
| Notes |
Based on the author's Ph. D. thesis, University of California, Berkeley, 1993 |
| Bibliography |
Includes bibliographical references (pages 73-78) and index |
| Notes |
Print version record |
| Subject |
NP-complete problems.
|
|
Computational complexity.
|
|
Automatic theorem proving.
|
|
Automatic theorem proving
|
|
Computational complexity
|
|
NP-complete problems
|
|
Polynomialzeitalgorithmus
|
|
Komplexitätsklasse
|
|
Beweis
|
|
Optimierungsproblem
|
|
NP-vollständiges Problem
|
|
Approximation
|
|
Complexité de calcul.
|
|
Théorèmes -- Démonstration automatique.
|
| Form |
Electronic book
|
| Author |
Sudan, Madhu.
|
| ISBN |
9783540484851 |
|
354048485X |
|
