Bounded query classes and the difference hierarchy (Q1114678)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4083607
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Bounded query classes and the difference hierarchy |
scientific article; zbMATH DE number 4083607 |
Statements
Bounded query classes and the difference hierarchy (English)
0 references
1989
0 references
Let A be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible to A based on bounding the number of queries to A that an oracle machine can make. When A is the halting problem K our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracle K.
0 references
hierarchy of sets
0 references
hierarchy of degrees
0 references
oracle machine
0 references
halting problem
0 references
parallel queries
0 references
serial queries
0 references
0 references
0.8387275
0 references
0.8344552
0 references
0 references
0 references
0.8304436
0 references
0.8240894
0 references
