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

jumprecursively enumerable setsemirecursive setfrequency computationquery hierarchybounded query reduction

Mathematics Subject Classification ID

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

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

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

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