Randomness and Completeness in Computational Complexity

Randomness and Completeness in Computational Complexity

by Dieter van Melkebeek


Want it by Friday, December 21 Order now and choose Expedited Shipping during checkout.

Product Details

ISBN-13: 9783540414926
Publisher: Springer Berlin Heidelberg
Publication date: 01/25/2001
Series: Lecture Notes in Computer Science , #1950
Edition description: 2000
Pages: 198
Product dimensions: 6.10(w) x 9.25(h) x 0.02(d)

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.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews