Randomness and Completeness in Computational Complexity

ISBN-13: 9783540414926 / Angielski / Miękka / 2000 / 198 str.

Dieter van Melkebeek

Opis

This text is based on the author's PhD thesis which was selected as the winning thesis of the 1999 ACM Doctoral Dissertation Competition. Dieter van Melkebeek did his PhD work at the University of Chicago with Lance Fortnow as thesis advisor. This work studies some central issues in computational complexity: the relative power of time, space, and randomness in computing and verification. The author develops techniques for separating complexity classes by isolating structural differences between their complete problems. He presents several approaches based on such diverse concepts as density, redundancy, and frequency of occurrence.

Spis treści

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.