2 options
Randomness and completeness in computational complexity / Dieter van Melkebeek.
LIBRA QA76.9.M35 M54 2000
Available from offsite location
LIBRA Q341 .P7 2004
Available from offsite location
- Format:
- Book
- Author/Creator:
- Melkebeek, Dieter van.
- Series:
- Lecture notes in computer science 0302-9743 ; 1950.
- Lecture notes in computer science, 0302-9743 ; 1950
- Language:
- English
- Subjects (All):
- Computer science--Mathematics.
- Computer science.
- Computational complexity.
- Physical Description:
- xv, 196 pages : illustrations ; 24 cm.
- Place of Publication:
- Berlin ; New York : Springer, [2000]
- 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 occurrence.
- Notes:
- Revision of thesis (Ph. D.)--University of Chicago, 1999.
- Includes bibliographical references (pages [183]-189) and indexes.
- ISBN:
- 3540414924
- OCLC:
- 45582464
The Penn Libraries is committed to describing library materials using current, accurate, and responsible language. If you discover outdated or inaccurate language, please fill out this feedback form to report it and suggest alternative language.