The complexity of ODDnA

DOI10.2307/2586523zbMATH Open0953.03051OpenAlexW2575237024MaRDI QIDQ4953205FDOQ4953205

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• One way functions and pseudorandom generators
• Parity, circuits, and the polynomial-time hierarchy
• The Degrees of Hyperimmune Sets
• Frequency computation and bounded queries
• Bounded queries in recursion theory
• Terse, superterse, and verbose sets
• Enumerative counting is hard
• Effective Search Problems
• Bounded query classes and the difference hierarchy
• Convex subsets of \(2^n\) and bounded truth-table reducibility
• Mathematical foundations of computer science 1996. 21st international symposium, MFCS '96, Cracow, Poland, September 2--6, 1996. Proceedings

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)