rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Randomness and Completeness in Computational Complexity
  name:
    name part: Melkebeek, Dieter van.
    role:
      role term: creator
    role:
      role term: author.
    role:
      role term: aut
    role:
      role term: http://id.loc.gov/vocabulary/relators/aut
  name:
    name part: SpringerLink (Online service)
  type of resource: text
  origin info:
    place:
      place term: gw
    date issued: 2000
    edition: 1st ed. 2000.
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: electronic
    form: electronic resource
    reformatting quality: access
    form: remote
    extent: XIII, 198 p. online resource.
  abstract: 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 ACM Doctoral Dissertation Award in May 2000. Summary Computational complexity is the study of the inherent di culty of compu- tional problems and the power of the tools we may use to solve them. It aims to describe how many resources we need to compute the solution as a function of the problem size. Typical resources include time on sequential and parallel architectures and memory space. As we want to abstract away from details of input representation and speci cs of the computer model, we end up with classes of problems that we can solve within certain robust resource bounds such as polynomial time, parallel logarithmic time, and logarithmic space. Research in complexity theory boils down to determining the relationships between these classes { inclusions and separations. In this dissertation, we focus on the role of randomness and look at various properties of hard problems in order to obtain separations. We also investigate the power of nondeterminism and alternation, as well as space versus time issues. Randomness provides a resource that seems to help in various situations.
  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.
  note: by Dieter van Melkebeek.
  subject:
    topic: Computer programming
  subject:
    topic: Computers
  subject:
    topic: Algorithms
  subject:
    topic: Computer logic
  subject:
    topic: Programming Techniques
  subject:
    topic: Theory of Computation
  subject:
    topic: Algorithm Analysis and Problem Complexity
  subject:
    topic: Computation by Abstract Devices
  subject:
    topic: Logics and Meanings of Programs
  classification: QA76.6-76.66
  classification: 005.11
  related item:
    title info:
      title: Springer eBooks
  related item:
    title info:
      title: Lecture Notes in Computer Science, 1950
  identifier: 9783540445456
  identifier: https://doi.org/10.1007/3-540-44545-5
  record info:
    record creation date: 121227
    record change date: 20191022031523.0
    record identifier: 978-3-540-44545-6