Randomness and Completeness in Computational Complexity
This book contains a revised version of the dissertation the author wrote at the Department of Computer Science of the University of Chicago. The thesis was submitted to the Faculty of Physical Sciences in conformity with the requirements for the PhD degree in June 1999. It was honored with the 1999...
Main Author: | |
---|---|
Corporate Author: | |
Format: | Electronic eBook |
Language: | English |
Published: |
Berlin, Heidelberg :
Springer Berlin Heidelberg : Imprint: Springer,
2000.
|
Edition: | 1st ed. 2000. |
Series: | Lecture Notes in Computer Science,
1950 |
Subjects: | |
Online Access: | Full Text via HEAL-Link |
Table of Contents:
- 1. Introduction
- 2. Preliminaries
- 3. Derandomizing Arthur-Merlin Games
- 4. Sparseness of Complete Languages
- 5. Autoreducibility of Complete Languages
- 6. The Size of Randomized Polynomial Time
- 7. The Frequency of Complete Languages
- 8. The Frequency of Autoreducible Languages.