Bounded Queries in Recursion Theory

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.00

or 4 interest-free payments of $42.25 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 $79.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

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.

Bounded Queries in Recursion Theory

At a Glance

Hardcover

Industry Reviews

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Computer Science

Python Crash Course

3rd Edition - A Hands-On, Project-Based Introduction to Programming

Microsoft 365 Excel All-in-One For Dummies

Excel for Dummies

The New Age of Sexism

How the AI Revolution is Reinventing Misogyny

The AI Con

How To Fight Big Tech's Hype and Create the Future We Want

Microsoft 365 Excel For Dummies

For Dummies (Computer/Tech)

If Anyone Builds It, Everyone Dies

The Case Against Superintelligent AI

Nexus

A Brief History of Information Networks from the Stone Age to AI

Creative Machines

AI, Art & Us

The AI-Driven Leader

Harnessing AI to Make Faster, Smarter Decisions

Genesis

Artificial Intelligence, Hope, and the Human Spirit

The Tech Coup

How to Save Democracy from Silicon Valley

The Coming Wave

AI, Power and the 21st Century's Greatest Dilemma

New Beginnings

why change is so difficult and how to achieve it

The Shortest History of AI

Building Machine Learning Systems with a Feature Store

Batch, Real-Time, and LLM Systems

Python Workout, Second Edition

200 ten-minute exercises

Life 3.0

Being Human in the Age of Artificial Intelligence

Python All-in-One For Dummies

3rd Edition

Artificial Intelligence

A Modern Approach, 4th Global Edition

Falter

Has the Human Game Begun to Play Itself Out?

Storytelling with Data

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

Effective Modern C++

42 Specific Ways to Improve Your Use of C++11 And C++14

Scary Smart

The Future of Artificial Intelligence and How You Can Save Our World

Fundamentals of Software Architecture

A Modern Engineering Approach

This product is categorised by