On computing Boolean connectives of characteristic functions

DOI10.1007/BF01303054zbMath0827.68065OpenAlexW1991109776WikidataQ59795820 ScholiaQ59795820MaRDI QIDQ4835862

Richard Chang, Jim Kadin

Publication date: 8 June 1995

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01303054

zbMATH Keywords

Boolean hierarchyNP complete setsquery hierarchies

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (18)

Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete ⋮ A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ Intersection suffices for Boolean hierarchy equivalence ⋮ Characteristics of multiple viewpoints in abstract argumentation ⋮ Completeness results for graph isomorphism. ⋮ Parameterized random complexity ⋮ Two queries ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ Complexity of stability ⋮ Complexity of Stability. ⋮ Lower Bounds for Kernelizations and Other Preprocessing Procedures ⋮ Lower bounds for kernelizations and other preprocessing procedures ⋮ The 1-versus-2 queries problem revisited ⋮ The computational complexity of ideal semantics ⋮ Commutative queries ⋮ Bounded queries, approximations, and the Boolean hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• The complexity of facets (and some facets of complexity)
• Polynomial terse sets
• The complexity of optimization problems
• Graph isomorphism is in the low hierarchy
• Bounded queries to SAT and the Boolean hierarchy
• A comparison of polynomial time reducibilities
• Some connections between bounded query classes and non-uniform complexity.
• On unique satisfiability and the threshold behavior of randomized reductions
• The difference and truth-table hierarchies for NP
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection

This page was built for publication: On computing Boolean connectives of characteristic functions