Bounded queries to arbitrary sets
From MaRDI portal
Publication:4717045
DOI10.1051/ITA/1996300200911zbMATH Open0860.68047OpenAlexW132066155MaRDI QIDQ4717045FDOQ4717045
Authors:
Publication date: 13 April 1997
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92532
Recommendations
Cites Work
- The complexity of combinatorial problems with succinct input representation
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- Bounded queries to SAT and the Boolean hierarchy
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- A comparison of polynomial time reducibilities
- A complexity theory for feasible closure properties
- Some connections between bounded query classes and non-uniform complexity.
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- On the Structure of Bounded Queries to Arbitrary NP Sets
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Relating Equivalence and Reducibility to Sparse Sets
Cited In (10)
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Lower bounds for set intersection queries
- On bounded query machines
- The expressive power of cardinality-bounded set values in object-based data models
- Title not available (Why is that?)
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)
