The Resource Bounded Queries in Recursion Theory, by William Levine, Georgia Martin, (electronic resource)

Bounded Queries in Recursion Theory, by William Levine, Georgia Martin, (electronic resource)

Label
Bounded Queries in Recursion Theory
Title
Bounded Queries in Recursion Theory
Statement of responsibility
by William Levine, Georgia Martin
Creator
Contributor
Author
Author
Subject
Language
  • eng
  • eng
Summary
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
Member of
http://library.link/vocab/creatorName
Levine, William
Dewey number
004.0151
http://bibfra.me/vocab/relation/httpidlocgovvocabularyrelatorsaut
  • oqhu87p5RRU
  • srLOIOBH5vM
Image bit depth
0
Language note
English
LC call number
QA76.9.M35
Literary form
non fiction
Nature of contents
dictionaries
http://library.link/vocab/relatedWorkOrContributorName
Martin, Georgia.
Series statement
Progress in Computer Science and Applied Logic,
Series volume
16
http://library.link/vocab/subjectName
  • Computer science
  • Operator theory
  • Information theory
  • Computational complexity
  • Computer science
  • Mathematics
  • Math Applications in Computer Science
  • Operator Theory
  • Theory of Computation
  • Discrete Mathematics in Computer Science
  • Computational Mathematics and Numerical Analysis
  • Applications of Mathematics
Label
Bounded Queries in Recursion Theory, by William Levine, Georgia Martin, (electronic resource)
Instantiates
Publication
Note
Bibliographic Level Mode of Issuance: Monograph
Antecedent source
mixed
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Color
not applicable
Content category
text
Content type code
txt
Contents
A: Getting Your Feet Wet -- 1 Basic Concepts -- 2 Bounded Queries and the Halting Set -- 3 Definitions and Questions -- B: The Complexity of Functions -- 4 The Complexity of CnA -- 5 #nA and Other Functions -- C: The Complexity of Sets -- 6 The Complexity of ODDnA and MODmnA -- 7 Q Versus QC -- 8 Separating and Collapsing Classes -- D: Miscellaneous -- 9 Nondeterministic Complexity -- 10 The Literature on Bounded Queries -- References
Dimensions
unknown
Edition
1st ed. 1999.
Extent
1 online resource (XIII, 353 p.)
File format
multiple file formats
Form of item
online
Isbn
9781461206354
Level of compression
uncompressed
Media category
computer
Media type code
c
Other control number
10.1007/978-1-4612-0635-4
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
  • (CKB)3400000000089210
  • (SSID)ssj0000933671
  • (PQKBManifestationID)11513292
  • (PQKBTitleCode)TC0000933671
  • (PQKBWorkID)10891399
  • (PQKB)10362828
  • (DE-He213)978-1-4612-0635-4
  • (MiAaPQ)EBC3074775
  • (EXLCZ)993400000000089210
Label
Bounded Queries in Recursion Theory, by William Levine, Georgia Martin, (electronic resource)
Publication
Note
Bibliographic Level Mode of Issuance: Monograph
Antecedent source
mixed
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Color
not applicable
Content category
text
Content type code
txt
Contents
A: Getting Your Feet Wet -- 1 Basic Concepts -- 2 Bounded Queries and the Halting Set -- 3 Definitions and Questions -- B: The Complexity of Functions -- 4 The Complexity of CnA -- 5 #nA and Other Functions -- C: The Complexity of Sets -- 6 The Complexity of ODDnA and MODmnA -- 7 Q Versus QC -- 8 Separating and Collapsing Classes -- D: Miscellaneous -- 9 Nondeterministic Complexity -- 10 The Literature on Bounded Queries -- References
Dimensions
unknown
Edition
1st ed. 1999.
Extent
1 online resource (XIII, 353 p.)
File format
multiple file formats
Form of item
online
Isbn
9781461206354
Level of compression
uncompressed
Media category
computer
Media type code
c
Other control number
10.1007/978-1-4612-0635-4
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
  • (CKB)3400000000089210
  • (SSID)ssj0000933671
  • (PQKBManifestationID)11513292
  • (PQKBTitleCode)TC0000933671
  • (PQKBWorkID)10891399
  • (PQKB)10362828
  • (DE-He213)978-1-4612-0635-4
  • (MiAaPQ)EBC3074775
  • (EXLCZ)993400000000089210

Library Locations

  • Architecture LibraryBorrow it
    Gould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US
    35.205706 -97.445050
  • Bizzell Memorial LibraryBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Boorstin CollectionBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Chinese Literature Translation ArchiveBorrow it
    401 W. Brooks St., RM 414, Norman, OK, 73019, US
    35.207487 -97.447906
  • Engineering LibraryBorrow it
    Felgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US
    35.205706 -97.445050
  • Fine Arts LibraryBorrow it
    Catlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US
    35.210371 -97.448244
  • Harry W. Bass Business History CollectionBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • History of Science CollectionsBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • John and Mary Nichols Rare Books and Special CollectionsBorrow it
    401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • Library Service CenterBorrow it
    2601 Technology Place, Norman, OK, 73019, US
    35.185561 -97.398361
  • Price College Digital LibraryBorrow it
    Adams Hall 102 307 West Brooks St., Norman, OK, 73019, US
    35.210371 -97.448244
  • Western History CollectionsBorrow it
    Monnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US
    35.209584 -97.445414
Processing Feedback ...