The Boolean Hierarchy I: Structural Properties
From MaRDI portal
Publication:3832042
Recommendations
Cited in
(75)- Exact complexity of exact-four-colorability
- The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
- Polynomial terse sets
- Complexity classes without machines: on complete languages for UP
- Bounded query classes and the difference hierarchy
- On truth-table reducibility to SAT
- A uniform approach to define complexity classes
- Boolean operations, joins, and the extended low hierarchy
- The random oracle hypothesis is false
- Universally serializable computation
- A second step towards complexity-theoretic analogs of Rice's Theorem
- The closure of monadic NP
- Reducing the number of solutions of NP functions
- On the complexity of automatic complexity
- Commutative queries
- Bounded queries, approximations, and the Boolean hierarchy
- Reasoning with power defaults
- Cognitive hierarchy and voting manipulation in \(k\)-approval voting
- From NP-completeness to DP-completeness: a membrane computing perspective
- Acceptance in incomplete argumentation frameworks
- On qualitative route descriptions. Representation, agent models, and computational complexity
- A complexity theory for feasible closure properties
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- All superlinear inverse schemes are coNP-hard
- Resource bounded immunity and simplicity
- A note on parallel queries and the symmetric-difference hierarchy.
- Cluster computing and the power of edge recognition
- Function operators spanning the arithmetical and the polynomial hierarchy
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games
- STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- scientific article; zbMATH DE number 3988706 (Why is no real title available?)
- scientific article; zbMATH DE number 4045650 (Why is no real title available?)
- The difference and truth-table hierarchies for NP
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- The Boolean Hierarchy II: Applications
- Mind change speed-up for learning languages from positive data
- scientific article; zbMATH DE number 17529 (Why is no real title available?)
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- On the power of deterministic reductions to C=P
- Query Order
- scientific article; zbMATH DE number 1222828 (Why is no real title available?)
- scientific article; zbMATH DE number 1500515 (Why is no real title available?)
- scientific article; zbMATH DE number 1747443 (Why is no real title available?)
- Characterizing and extending answer set semantics using possibility theory
- A survey on difference hierarchies of regular languages
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- On Existentially First-Order Definable Languages and Their Relation to NP
- scientific article; zbMATH DE number 1839454 (Why is no real title available?)
- On computing Boolean connectives of characteristic functions
- Fine hierarchies and Boolean terms
- Strong self-reducibility precludes strong immunity
- A downward translation in the polynomial hierarchy
- The complexity class θp2: Recent results and applications in AI and modal logic
- Query order in the polynomial hierarchy
- Reductions to sets of low information content (extended abstract)
- A relationship between difference hierarchies and relativized polynomial hierarchies
- On the power of parity polynomial time
- The strong exponential hierarchy collapses
- On boolean lowness and boolean highness
- Intersection suffices for Boolean hierarchy equivalence
- From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules
- Observations on complete sets between linear time and polynomial time
- Pinpointing computation with modular queries in the Boolean hierarchy
- Broadcast graph is NP-complete
- Quantum sat problems with finite sets of projectors are complete for a plethora of classes
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
- New developments in structural complexity theory
- Kolmogorov complexity and degrees of tally sets
- On the complexity of test case generation for NP-hard problems
- The Boolean hierarchy of NP-partitions
- The complexity of unions of disjoint sets
- The 1-versus-2 queries problem revisited
This page was built for publication: The Boolean Hierarchy I: Structural Properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3832042)
