The complexity of ODDnA
From MaRDI portal
Publication:4953205
jumprecursively enumerable setsemirecursive setfrequency computationquery hierarchybounded query reduction
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Hierarchies of computability and definability (03D55) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10) Other degrees and reducibilities in computability and recursion theory (03D30)
Recommendations
Cites work
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Bounded queries in recursion theory
- Bounded query classes and the difference hierarchy
- Convex subsets of \(2^n\) and bounded truth-table reducibility
- Effective Search Problems
- Enumerative counting is hard
- Frequency computation and bounded queries
- Mathematical foundations of computer science 1996. 21st international symposium, MFCS '96, Cracow, Poland, September 2--6, 1996. Proceedings
- One way functions and pseudorandom generators
- Parity, circuits, and the polynomial-time hierarchy
- Terse, superterse, and verbose sets
- The Degrees of Hyperimmune Sets
Cited in
(7)- Query complexity of membership comparable sets.
- Terse, superterse, and verbose sets
- Nondeterministic bounded query reducibilities
- Some connections between bounded query classes and non-uniform complexity.
- Choosing, agreeing, and eliminating in communication complexity
- The communication complexity of enumeration, elimination, and selection
- Regularity versus complexity in the binary representation of 3^n
This page was built for publication: The complexity of ODDnA
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4953205)