Bounded queries to arbitrary sets
From MaRDI portal
Publication:4717045
Recommendations
Cites work
- A comparison of polynomial time reducibilities
- A complexity theory for feasible closure properties
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Bounded queries to SAT and the Boolean hierarchy
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- On the Structure of Bounded Queries to Arbitrary NP Sets
- Relating Equivalence and Reducibility to Sparse Sets
- Some connections between bounded query classes and non-uniform complexity.
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- The complexity of combinatorial problems with succinct input representation
Cited in
(10)- scientific article; zbMATH DE number 1114037 (Why is no real title available?)
- scientific article; zbMATH DE number 1405575 (Why is no real title available?)
- Bounded query classes and the difference hierarchy
- A Theory of Local Set Queries
- On Bounded Queries and Approximation
- On the Structure of Bounded Queries to Arbitrary NP Sets
- scientific article; zbMATH DE number 1424049 (Why is no real title available?)
- Lower bounds for set intersection queries
- On bounded query machines
- The expressive power of cardinality-bounded set values in object-based data models
This page was built for publication: Bounded queries to arbitrary sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4717045)
