Progress in Computer Science and Applied Logic

By: William I. Gasarch, G. Martin, W. Gasarch

Write A Review

Hardcover | 23 December 1998

At a Glance

Hardcover
376 Pages

Dimensions(cm)
24.77 x 16.51 x 2.54

Hardcover

$169.75

or 4 interest-free payments of $42.44 with

Ships in 5 to 7 business days

One of the major concerns of theoretical computer science is the classifi cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have also been considered. In recursion theory, by contrast, a function is considered to be easy to compute if there exists some algorithm that computes it. We wish to classify functions that are hard, i.e., not computable, in a quantitative way. We cannot use time or space, since the functions are not even computable. We cannot use Turing degree, since this notion is not quantitative. Hence we need a new notion of complexity-much like time or spac~that is quantitative and yet in some way captures the level of difficulty (such as the Turing degree) of a function.

Industry Reviews

"Ideal for an advanced undergraduate or beginning graduate student who has some exposure to basic computability theory and wants to see what one can do with it. The questions asked are interesting and can be easily understood and the proofs can be followed without a large amount of training in computability theory."

--Sigact News

Shipping

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

Orders over $89.00 qualify for free shipping.

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 Mathematics Mathematical Foundation Mathematical Logic Applied Mathematics Combinatorics & Graph Theory Computing & I.T.Databases Data Capture & Analysis Calculus & Mathematical Analysis Functional Analysis & Transforms Computer Science

Mathematical Theory of Computation Maths for Computer Scientists Gardening Numerical Analysis

Preface
Getting Your Feet Wet	p. 1
Basic Concepts	p. 3
Bounded Queries and the Halting Set	p. 43
Definitions and Questions	p. 53
The Complexity of Functions	p. 75
The Complexity of C[subscript n][superscript A]	p. 77
#[subscript n][superscript A] and Other Functions	p. 143
The Complexity of Sets	p. 183
The Complexity of ODD[subscript n][superscript A] and MODm[subscript n][superscript A]	p. 185
Q Versus QC	p. 217
Separating and Collapsing Classes	p. 255
Miscellaneous	p. 271
Nondeterministic Complexity	p. 273
The Literature on Bounded Queries	p. 295
References	p. 325
Index	p. 331
Table of Contents provided by Blackwell. All Rights Reserved.

Progress in Computer Science and Applied Logic

At a Glance

Hardcover

Industry Reviews

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Applied Mathematics

Stochastic Control in Energy, Environmental and Resource Management Applications

Emerging Methodologies and Applications in Modelling, Identification and Control

Applied Multivariate Statistical Analysis

Volume 1

Advances in Numerical Methods and Analysis

The Gamma Function (Advanced Topics in Mathematics)

Advanced Topics in Mathematics

Storytelling with Data

1st Edition - A Data Visualization Guide for Business Professionals

Game Theory

2nd edition

Bird's Engineering Mathematics

9th Edition

Basic Math & Pre-Algebra For Dummies Book + Workbook Bundle

For Dummies Math & Science

Bird's Higher Engineering Mathematics

9th Edition

Introduction to Stochastic Processes

2nd Edition

Essentials of Medical Statistics

2nd Edition

A Mind for Numbers

How to Excel at Math and Science (Even If You Flunked Algebra)

Engineering Mathematics

5th edition

Introduction to Probability

2nd edition

Swim Training Patterns

1st Edition - Plan your Training Sessions with the Power of Mathematics

Storytelling with Data

A Data Visualization Guide for Business Professionals, 10th Anniversary Edition

Life Lessons from Game Theory

The Art of Thinking Strategically in a Complex World

Intermediate Financial Theory

3rd Edition

Elementary Linear Algebra

8th Edition - International Metric Edition

MATLAB

6th Edition - A Practical Introduction to Programming and Problem Solving

Cookbooks (O'Reilly)

Cookbooks (O'Reilly)

Alex's Adventures in Numberland

Tenth Anniversary Edition

Everything Is Predictable

How Bayes' Remarkable Theorem Explains the World

Making Sense of Chaos

A Better Economics for a Better World

This product is categorised by