Custom cover image
Custom cover image

Randomness and Completeness in Computational Complexity / by Dieter Melkebeek

By: Resource type: Ressourcentyp: Buch (Online)Book (Online)Language: English Series: SpringerLink Bücher | Springer eBook Collection Computer Science | Lecture notes in computer science ; 1950Publisher: Berlin, Heidelberg : Springer-Verlag Berlin Heidelberg, 2000Description: Online-RessourceISBN:
  • 9783540445456
  • 3540414924
Subject(s): Genre/Form: Additional physical formats: 9783540414926 | Buchausg. u.d.T.: Randomness and completeness in computational complexity. Berlin : Springer, 2000. XV, 196 S.DDC classification:
  • 004.0151
  • 004/.01/51
  • 005.1 23
  • 005.11 23
MSC: MSC: *68Q25 | 68-02RVK: RVK: ST 134 | SS 4000LOC classification:
  • QA76.9.A43
DOI: DOI: 10.1007/3-540-44545-5Online resources: Summary: This book is based on the author's Ph.D. thesis which was selected as the winning thesis of the 1999 ACM Doctoral Dissertation Competition. Dieter van Melkebeek did his Ph.D. 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 occurrencePPN: PPN: 1649249594Package identifier: Produktsigel: ZDB-2-BAE | ZDB-2-LNC | ZDB-2-SCS | ZDB-2-SXCS | ZDB-2-SEB
No physical items for this record
KIT – The University in the Helmholtz Association                         Home | Impressum | Datenschutz | Barrierefreiheit | KIT