Bounded queries to arbitrary sets

DOI10.1051/ita/1996300200911zbMath0860.68047OpenAlexW132066155MaRDI QIDQ4717045

No author found.

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

zbMATH Keywords

hierarchy of sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• The complexity of combinatorial problems with succinct input representation
• Bounded queries to SAT and the Boolean hierarchy
• A comparison of polynomial time reducibilities
• Some connections between bounded query classes and non-uniform complexity.
• A complexity theory for feasible closure properties
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• On the Structure of Bounded Queries to Arbitrary NP Sets
• Relating Equivalence and Reducibility to Sparse Sets
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• A relationship between difference hierarchies and relativized polynomial hierarchies

This page was built for publication: Bounded queries to arbitrary sets