The complexity of ODDnA

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

zbMATH Keywords

recursively enumerable setsemirecursive setjumpfrequency computationquery hierarchybounded query reduction

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10) Hierarchies of computability and definability (03D55)

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 ODD_n^A