Detailansicht
Bounded Queries in Recursion Theory
Progress in Computer Science and Applied Logic 16
ISBN/EAN: 9780817639662
Umbreit-Nr.: 1652291
Sprache:
Englisch
Umfang: xiii, 353 S.
Format in cm: 2.4 x 24.2 x 16.1
Einband:
gebundenes Buch
Erschienen am 23.12.1998
- Zusatztext
- 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.
- Autorenportrait
- InhaltsangabeA: Getting Your Feet Wet.- 1 Basic Concepts.- 1.1 Notation, Conventions, and Definitions.- 1.2 Basic Recursion Theory.- 1.2.1 Recursive and Recursively Enumerable Sets.- 1.2.2 Reductions.- 1.2.3 Jump and the Arithmetic Hierarchy.- 1.2.4 Simulation and Dovetailing.- 1.3 Useful Concepts from Recursion Theory.- 1.3.1 The Recursion Theorem.- 1.3.2 Initial Segment Arguments.- 1.4 Advanced Concepts We Will Need.- 1.5 Exercises.- 1.6 Bibliographic Notes.- 2 Bounded Queries and the Halting Set.- 2.1 Basic Results About K.- 2.2 Exercises.- 2.3 Bibliographic Notes.- 3 Definitions and Questions.- 3.1 Definitions of Classes.- 3.2 Questions We Address.- 3.3 Enumerability and Bounded Queries.- 3.4 Uniformity.- 3.5 Order Notation.- 3.6 Exercises.- 3.7 Bibliographic Notes.- B: The Complexity of Functions.- 4 The Complexity of CnA.- 4.1 A General Lower Bound.- 4.2 Class Separation: FQ(n,A) ? FQ(n+ 1,A).- 4.3 Verbose Sets.- 4.4 Non-superterse Sets Are Semiverbose.- 4.5 Superterse Sets.- 4.6 Semiverbose Sets.- 4.7 Most Sets Are Superterse.- 4.7.1 The Set of Superterse Sets Has Measure 1.- 4.7.2 The Set of Superterse Sets Is Co-meager.- 4.8 Recursively Enumerable Sets.- 4.8.1 Using Queries to Other Sets.- 4.8.2 Using Queries to A.- 4.8.3 An R.E. Terse Set in Every Nonzero R.E. Degree.- 4.9 Exercises.- 4.10 Bibliographic Notes.- 5 #nA and Other Functions.- 5.1 Trees.- 5.2 Ramsey Theory.- 5.3 Lower Bound on the Complexity of #nA.- 5.4 A General Theorem.- 5.5 Strong Class Separation: EN(2n - 1) ? FQ(n, A).- 5.6 An Alternative Proof.- 5.7 Exercises.- 5.8 Bibliographic Notes.- C: The Complexity of Sets.- 6 The Complexity of ODDnA and MODmnA.- 6.1 ODDnA for Semirecursive Sets A.- 6.2 ODDnA for R.E. Sets A.- 6.2.1 A Proof in the Spirit of Theorem 4.1.1.- 6.2.2 A Proof in the Spirit of Theorem 5.3.2.- 6.2.3 A Very Unusual Proof.- 6.3 The Complexity of MODmnA.- 6.4 ODDnA and MODmnA Can Be Easy.- 6.5 Exercises.- 6.6 Bibliographic Notes.- 7 Q Versus QC.- 7.1 Preliminaries.- 7.2 K Is U.C.- 7.3 Nonzero R.E. Degrees R.E.S.N.U.C.- 7.4 An Intermediate R.E. Set That Is U.C.- 7.5 A Completely R.E.S.N.U.C. Degree.- 7.6 Other U.C. Sets.- 7.7 Truth Table Degrees.- 7.8 Exercises.- 7.9 Bibliographic Notes.- 8 Separating and Collapsing Classes.- 8.1 Sets That Are Both Supportive and Parallel Supportive.- 8.2 Sets That Are Supportive but Not Parallel Supportive.- 8.3 Sets That Are Neither Supportive Nor Parallel Supportive.- 8.4 Exercises.- 8.5 Bibliographic Notes.- D: Miscellaneous.- 9 Nondeterministic Complexity.- 9.1 Nondeterministic Computation.- 9.2 Subjective Sets.- 9.3 Locally Subjective Sets.- 9.3.1 K Is Not Locally Subjective.- 9.3.2 There Exist Locally 1-Subjective Sets.- 9.3.3 Characterizing Locally 1-Subjective Sets.- 9.4 Exercises.- 9.5 Bibliographic Notes.- 10 The Literature on Bounded Queries.- References.