Bounded Queries in Recursion Theory

, by Gasarch, William I.; Martin, Georgia A.

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780817639662 | 0817639667
Cover: Hardcover
Copyright: 5/1/1999

Rent

(Recommended)

$124.02

Term

Due

Price

Semester

Dec 12

$130.55

Quarter

Aug 13

$124.02

Short Term

Jul 29

$117.50

*This item is part of an exclusive publisher rental program and requires an additional convenience fee. This fee will be reflected in the shopping bag.
Buy New

Special Order: 1-2 Weeks

$167.14
eBook

Available Instantly

Online: 180 Days

Downloadable: 180 Days

*To support the delivery of the digital material to you, a digital delivery fee of $3.99 will be charged on each digital item.

$77.22*

Focuses on the issue of measuring complexity by the number of queries to an oracle. Designed to classify certain functions in terms of the number of queries needed to compute them - & to determine when more queries can be used to compute more functions. Classifies functions that are not computable, in a quantitative way. DLC: Computational complexity.

Preface

PART A: GETTING YOUR FEET WET

(74)

Basic Concepts

(40)

Notation, Conventions, and Definitions

(7)

Basic Recursion Theory

(17)

Recursive and Recursively Enumerable Sets

(7)

Reductions

(8)

Jump and the Arithmetic Hierarchy

(1)

Simulation and Dovetailing

(1)

Useful Concepts from Recursion Theory

(7)

The Recursion Theorem

(3)

Initial Segment Arguments

(4)

Advanced Concepts We Will Need

(3)

Exercises

(5)

Bibliographic Notes

(1)

Bounded Queries and the Halting Set

(10)

Basic Results About K

(8)

Exercises

(1)

Bibliographic Notes

(1)

Definitions and Questions

(22)

Definitions of Classes

(3)

Questions We Address

(3)

Enumerability and Bounded Queries

(5)

Uniformity

(4)

Order Notation

(1)

Exercises

(4)

Bibliographic Notes

(2)

PART B: THE COMPLEXITY OF FUNCTIONS

(108)

The Complexity of CAn

(66)

A General Lower Bound

(5)

Class Separation: FQ(n, A) ⊂ FQ(n + 1, A)

(1)

Verbose Sets

(2)

Non-superterse Sets Are Semiverbose

(6)

Superterse Sets

(2)

Semiverbose Sets

(5)

Most Sets Are Superterse

(9)

The Set of Superterse Sets Has Measure 1

100

(4)

The Set of Superterse Sets Is Co-meager

104

(4)

Recursively Enumerable Sets

108

(27)

Using Queries to Other Sets

108

(1)

Using Queries to A

109

(10)

An R.E. Terse Set in Every Nonzero R.E. Degree

119

(16)

Exercises

135

(6)

Bibliographic Notes

141

(2)

#An and Other Functions

143

(40)

Trees

144

(5)

Ramsey Theory

149

(5)

Lower Bound on the Complexity of #An

154

(9)

A General Theorem

163

(4)

Strong Class Separation: EN(2n - 1) ⊂ FQ(n, A)

167

(5)

An Alternative Proof

172

(5)

Exercises

177

(5)

Bibliographic Notes

182

(1)

PART C: THE COMPLEXITY OF SETS

183

(88)

The Complexity of ODD An and MODm An

185

(32)

ODDAn for Semirecursive Sets A

186

(13)

ODDAn for R.E. Sets A

199

(6)

A Proof in the Spirit of Theorem 4.1.1

199

(3)

A Proof in the Spirit of Theorem 5.3.2

202

(2)

A Very Unusual Proof

204

(1)

The Complexity of MODmAn

205

(5)

ODDAn and MODmAn Can Be Easy

210

(1)

Exercises

210

(6)

Bibliographic Notes

216

(1)

Q Versus QC

217

(38)

Preliminaries

219

(1)

K Is U.C.

219

(2)

Nonzero R.E. Degrees R.E.S.N.U.C.

221

(3)

An Intermediate R.E. Set That Is U.C.

224

(3)

A Completely R.E.S.N.U.C. Degree

227

(10)

Other U.C. Sets

237

(10)

Truth Table Degrees

247

(5)

Exercises

252

(1)

Bibliographic Notes

253

(2)

Separating and Collapsing Classes

255

(16)

Sets That Are Both Supportive and Parallel Supportive

257

(1)

Sets That Are Supportive but Not Parallel Supportive

257

(11)

Sets That Are Neither Supportive Nor Parallel Supportive

268

(1)

Exercises

269

(1)

Bibliographic Notes

269

(2)

PART D: MISCELLANEOUS

271

(54)

Nondeterministic Complexity

273

(22)

Nondeterministic Computation

273

(5)

Subjective Sets

278

(2)

Locally Subjective Sets

280

(12)

K Is Not Locally Subjective

280

(3)

There Exist Locally 1-Subjective Sets

283

(1)

Characterizing Locally 1-Subjective Sets

284

(8)

Exercises

292

(1)

Bibliographic Notes

293

(2)

The Literature on Bounded Queries

295

(30)

References

325

(6)

Index

331

Please wait while the item is added to your bag...

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Bounded Queries in Recursion Theory

Summary

Table of Contents

Supplemental Materials

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Bounded Queries in Recursion Theory

Summary

Table of Contents

Supplemental Materials

Digital License