The complexity of ODDnA
From MaRDI portal
Publication:4953205
DOI10.2307/2586523zbMath0953.03051OpenAlexW2575237024MaRDI QIDQ4953205
Timothy H. McNicholl, Richard Beigel, Martin Kummer, William I. Gasarch, Georgia A. Martin, Frank Stephan
Publication date: 22 June 2000
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2586523
recursively enumerable setsemirecursive setjumpfrequency computationquery hierarchybounded query reduction
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (4)
Query complexity of membership comparable sets. ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Choosing, agreeing, and eliminating in communication complexity
Cites Work
- Unnamed Item
- Frequency computation and bounded queries
- One way functions and pseudorandom generators
- Bounded query classes and the difference hierarchy
- Convex subsets of \(2^n\) and bounded truth-table reducibility
- Terse, superterse, and verbose sets
- Bounded queries in recursion theory
- Enumerative counting is hard
- Mathematical foundations of computer science 1996. 21st international symposium, MFCS '96, Cracow, Poland, September 2--6, 1996. Proceedings
- Parity, circuits, and the polynomial-time hierarchy
- Effective Search Problems
- The Degrees of Hyperimmune Sets
This page was built for publication: The complexity of ODDnA
