GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Log in
  • Find a journal
  • Publish with us
  • Track your research
  • Saved research
  • Cart
  • Home
  • Journals A-Z
  • Books A-Z
  • Subjects A-Z
  • Journal finder
  • Language editing
  • Open access publishing
  • Our products

This view

  • Original page
  • New address

GeezerVison is showing link.springer.com — Randomness and Completeness in Computational Complexity

Overview

Authors:
  • Dieter Melkebeek 0
  1. Dieter Melkebeek
    1. Institute for Advanced Studies Einstein Drive, Princeton, NJ, USA

    View author publications

    Search author on: PubMed   Google Scholar

  • Includes supplementary material: sn.pub/extras

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1950)

  • 3269 Accesses

  • 9 Citations

  • 3 Altmetric

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 17.99 USD 54.99
Discount applied Price excludes VAT (USA)
  • Compact, lightweight edition
  • Free shipping worldwide - view details

Tax calculation will be finalised at checkout

Licence this eBook for your library
Learn about institutional subscriptions

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

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.

Similar content being viewed by others

Computational Complexity

Chapter © 2024

Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer

Chapter © 2018

Large simplicial complexes: universality, randomness, and ampleness

Article Open access 16 September 2023

Explore related subjects

Discover the latest articles, books and news in related subjects.
  • Computer Science Logic and Foundations of Programming
  • Algorithms
  • Programming Techniques
  • Theory of Computation
  • Algorithmic Information Theory and Its Applications

Table of contents (8 chapters)

  1. Front Matter

    Pages I-XV
    Download chapter PDF
  2. 1. Introduction

    • Dieter van Melkebeek
    Pages 1-11
  3. 2. Preliminaries

    • Dieter van Melkebeek
    Pages 13-52
  4. 3. Derandomizing Arthur-Merlin Games

    • Dieter van Melkebeek
    Pages 53-76
  5. 4. Sparseness of Complete Languages

    • Dieter van Melkebeek
    Pages 77-112
  6. 5. Autoreducibility of Complete Languages

    • Dieter van Melkebeek
    Pages 113-140
  7. 6. The Size of Randomized Polynomial Time

    • Dieter van Melkebeek
    Pages 141-144
  8. 7. The Frequency of Complete Languages

    • Dieter van Melkebeek
    Pages 145-159
  9. 8. The Frequency of Autoreducible Languages

    • Dieter van Melkebeek
    Pages 161-181
  10. Back Matter

    Pages 183-196
    Download chapter PDF
Back to top

Authors and affiliations

  • Institute for Advanced Studies Einstein Drive, Princeton, NJ, USA

    Dieter Melkebeek

Accessibility information

Accessibility information for this book is coming soon. We're working to make it available as quickly as possible. Thank you for your patience.

Bibliographic information

  • Book title: Randomness and Completeness in Computational Complexity

  • Authors: Dieter Melkebeek

  • Series title: Lecture Notes in Computer Science

  • DOI: https://doi.org/10.1007/3-540-44545-5

  • Publisher: Springer Berlin, Heidelberg

  • eBook packages: Springer Book Archive

  • Copyright information: Springer-Verlag Berlin Heidelberg 2000

  • Softcover ISBN: 978-3-540-41492-6Published: 13 December 2000

  • eBook ISBN: 978-3-540-44545-6Published: 29 June 2003

  • Series ISSN: 0302-9743

  • Series E-ISSN: 1611-3349

  • Edition number: 1

  • Number of pages: XIII, 198

  • Topics: Programming Techniques, Theory of Computation, Algorithm Analysis and Problem Complexity, Computation by Abstract Devices, Logics and Meanings of Programs

Keywords

  • Algorithms
  • Complete Languages
  • Completeness
  • Complexity Theory
  • Computational Complexity
  • Formal Language Theory
  • Game Theory
  • Randomness
  • Theoretical Computer Science
  • complexity
  • verification
  • algorithm analysis and problem complexity

Publish with us

Policies and ethics

Back to top
You are visitor 01402605 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.