The complexity of ODDnA

DOI10.2307/2586523MaRDI QIDQ4953205zbMATH OpenOpenAlexFDO

Authors Richard Beigel, Timothy H. McNicholl, William Gasarch, Martin Kummer, 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

bounded query reductionfrequency computationjumpquery hierarchyrecursively enumerable setsemirecursive set

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1114037
• Bounded queries to SAT and the Boolean hierarchy
• Nondeterministic bounded query reducibilities

Cites work

• 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
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• 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

(9)

• Nondeterministic bounded query reducibilities
• On checking versus evaluation of multiple queries
• Query complexity of membership comparable sets.
• Some connections between bounded query classes and non-uniform complexity.
• Terse, superterse, and verbose sets
• scientific article; zbMATH DE number 512828 (Why is no real title available?)
• Regularity versus complexity in the binary representation of 3ⁿ
• The communication complexity of enumeration, elimination, and selection
• Choosing, agreeing, and eliminating in communication complexity

This page was built for publication: The complexity of ODD_n^A

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4953205)