Lecture Notes in Computer Science

By: Dieter van Melkebeek

Write A Review

Paperback | 13 December 2000

At a Glance

Paperback
220 Pages

Dimensions(cm)
22.86 x 15.88 x 1.27

Paperback

$84.99

or 4 interest-free payments of $21.25 with

Ships in 5 to 7 business days

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.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Computing & I.T.Computer Science Mathematical Theory of Computation Mathematics Discrete Mathematics Computer Architecture & Logic Design Computer Programming & Software Development Algorithms & Data Structures

Introduction	p. 1
Issues in Computational Complexity	p. 1
The Power of Randomness	p. 1
The Power of Guessing	p. 5
The Power of Memory	p. 6
Contributions in This Dissertation	p. 8
Simulations	p. 8
Separations	p. 9
Preliminaries	p. 13
Computational Problems	p. 13
Models of Computation, Resource Bounds, and Complexity Classes	p. 18
Turing Machines	p. 19
Uniform Families of Boolean Circuits	p. 21
Nondeterministic Turing Machines	p. 24
Alternating Turing Machines	p. 27
Randomness	p. 31
Randomized Computations	p. 32
Randomized Proof Checking	p. 35
Pseudo-Random Generators	p. 37
Reductions and Completeness	p. 42
Relativization	p. 42
Reductions	p. 44
Complete Problems	p. 46
Resource-Bounded Measure	p. 47
Motivation	p. 47
Martingales	p. 48
Properties	p. 50
Derandomizing Arthur-Merlin Games	p. 53
Introduction	p. 53
Notation	p. 56
Derandomizing Arthur-Merlin Games	p. 57
Proof of Lemma 3.3.1	p. 60
Proof of Theorem 3.3.1	p. 61
Proof of Theorem 3.3.2	p. 63
A General Framework for Derandomization	p. 64
More Applications	p. 66
Valiant-Vazirani	p. 66
Learning Circuits	p. 69
Rigid Matrices	p. 70
Universal Traversal Sequences	p. 72
Conclusion and Open Questions	p. 76
Sparseness of Complete Languages	p. 77
Introduction	p. 77
The Sparse Hard Language Problem for NP	p. 77
The Sparse Hard Language Problem for P	p. 78
Overview of this Chapter	p. 79
Deterministic Reductions	p. 81
Previous Work	p. 81
Main Result	p. 85
Generic Theorem for P	p. 92
Extension to Classes Other Than P	p. 95
Randomized Reductions	p. 98
Previous Work	p. 98
Main Result	p. 99
Randomized Generic Theorem for P	p. 106
Extension to Classes Other Than P	p. 109
Conclusion and Open Questions	p. 112
Autoreducibility of Complete Languages	p. 113
Introduction	p. 113
Definitions	p. 115
Nonautoreducibility Results	p. 115
Adaptive Autoreductions	p. 116
Nonadaptive Autoreductions	p. 121
Autoreducibility Results	p. 122
Adaptive Autoreductions	p. 123
Nonadaptive Autoreductions	p. 130
Randomized and Nonuniform Autoreductions	p. 134
Separation Results	p. 137
Conclusion and Open Questions	p. 139
The Size of Randomized Polynomial Time	p. 141
Introduction	p. 141
The Zero-One Law for BPP	p. 142
Generalization	p. 143
Conclusion and Open Questions	p. 144
The Frequency of Complete Languages	p. 145
Introduction	p. 145
Complete Languages under Nonadaptive Reductions with n^¿ Queries and a Small Span Theorem	p. 146
Complete Languages for EXP under Adaptive Reductions with n^c Queries	p. 152
Complete Languages for EXP under Nonadaptive Reductions	p. 154
Conclusion and Open Questions	p. 159
The Frequency of Autoreducible Languages	p. 161
Introduction	p. 161
Betting Games	p. 163
From Betting Games to Martingales	p. 165
Sampling Results	p. 168
Autoreducible Languages	p. 172
Adaptively Autoreducible Languages	p. 172
Nonadaptively Autoreducible Languages	p. 174
Covering Autoreducible Languages by Martingales	p. 175
Conclusion and Open Questions	p. 181
References	p. 183
Notation Index	p. 191
Subject Index	p. 195
Table of Contents provided by Publisher. All Rights Reserved.

Lecture Notes in Computer Science

At a Glance

Paperback

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Algorithms & Data Structures

The Man Who Solved the Market

How Jim Simons Launched the Quant Revolution SHORTLISTED FOR THE FT & MCKINSEY BUSINESS BOOK OF THE YEAR AWARD 2019

Algorithms in C, Parts 1-4

3rd Edition - Fundamentals, Data Structures, Sorting, Searching

The Delicate Art of Brute Force

How to Compute It When You Can't Solve It

Introduction to Machine Learning with Python

A Guide for Data Scientists

Code Dependent

Living in the Shadow of AI - Shortlisted for the Women's Prize for Non-Fiction

Python for Algorithmic Trading

From Idea to Cloud Deployment

Learning Algorithms

A Programmer's Guide to Writing Better Code

Finite Element Mesh Generation, 2e

Quantum Searching and Optimization Algorithms

A Comprehensive Guide

Python Using GPT-5 and Gemini

Decentralized Futures

Navigating the Integration of Blockchain Technology with Artificial Intelligence

Fundamentals of Data Structures and Algorithms

Fundamentals of Data Structures and Algorithms

Considerations on the AI Endgame

Ethics, Risks and Computational Frameworks

Artificial Intelligence for Art Creation and Understanding

Multimedia Computing, Communication and Intelligence

Quick Data Structures

Quick Programming

Hacker's Delight

Artificial Intelligence Programming with Python

From Zero to Hero

Quantum Machine Learning

Theory, Algorithms, and Practical Implementation

The Algorithmic Society

Technology, Power, and Knowledge

Head First Algorithms and Data Structures

A Learner's Guide to the Foundations of Computing

Computational Intractability

A Guide to Algorithmic Lower Bounds

Deep Learning with R, Third Edition

Development of Multi-Agent Systems Infrastructures

A Practical Approach

This product is categorised by