Randomness and Completeness in Computational Complexity

• Κύριος συγγραφέας: Melkebeek, Dieter van (Συγγραφέας, http://id.loc.gov/vocabulary/relators/aut)
• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2000.
• Έκδοση: 1st ed. 2000.
• Σειρά: Lecture Notes in Computer Science, 1950
• Θέματα: Computer programming.; Computers.; Algorithms.; Computer logic.; Programming Techniques.; Theory of Computation.; Algorithm Analysis and Problem Complexity.; Computation by Abstract Devices.; Logics and Meanings of Programs.

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...

Πίνακας περιεχομένων:

• 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.