GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing link.springer.com — Randomness and Completeness in Computational Complexity Overview
Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1950)
This is a preview of subscription content, log in via an institution to check access. Access this book
Softcover Book
USD 17.99
Discount applied Price excludes VAT (USA)
Tax calculation will be finalised at checkout Other ways to accessAbout 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 othersComputational Complexity
Chapter
© 2024
![]() Large simplicial complexes: universality, randomness, and ampleness
Article
Open access
16 September 2023
Explore related subjectsDiscover the latest articles, books and news in related subjects.Table of contents (8 chapters)
Authors and affiliations
Accessibility informationAccessibility 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
KeywordsPublish with us |
| 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. |