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...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Médium: | Livre numérique |
| Jazyk: | Anglais |
| Vydáno: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Edice: | Lecture notes in computer science
1950 |
| Témata: | |
| On-line přístup: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Poznámka: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Randomness and completeness in computational complexity, Dieter van Melkebeek, 2000, New York, Springer, 1 vol. (XV-196 p.), Lecture notes in computer science, 3-540-41492-4 • Randomness and Completeness in Computational Complexity, Texte imprimé, 9783662202166 |
Obsah:
- 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.