On computing Boolean connectives of characteristic functions

DOI10.1007/BF01303054zbMATH Open0827.68065OpenAlexW1991109776WikidataQ59795820 ScholiaQ59795820MaRDI QIDQ4835862FDOQ4835862

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)

Cites Work

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

Cited In (25)

• Commutative queries
• Lower bounds for kernelizations and other preprocessing procedures
• Completeness results for graph isomorphism.
• The 1-versus-2 queries problem revisited
• The computational complexity of ideal semantics
• Numerical computation of characteristic polynomials of Boolean functions and its applications
• Relativized logspace and generalized quantifiers over finite ordered structures
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Complexity of stability
• Characterizing Negabent Boolean Functions over Finite Fields
• Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games
• Approximate evaluations of characteristic polynomials of Boolean functions
• Two queries
• Title not available (Why is that?)
• Intersection suffices for Boolean hierarchy equivalence
• Lower Bounds for Kernelizations and Other Preprocessing Procedures
• Characteristics of multiple viewpoints in abstract argumentation
• Parameterized random complexity
• Characterization of Boolean valued star and mega lattice functions
• Trading properties and Alexandrov kernels for Boolean functions
• Bounded queries, approximations, and the Boolean hierarchy
• Character analogue of the Boole summation formula with applications
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Complexity of Stability.
• The 1-Versus-2 Queries Problem Revisited

Recommendations

• On the multiplicative complexity of some Boolean functions 👍 👎
• Equational characterizations of Boolean function classes 👍 👎
• Characterizing Negabent Boolean Functions over Finite Fields 👍 👎
• On connected Boolean functions 👍 👎
• The complexity of Boolean functions in different characteristics 👍 👎
• Approximate evaluations of characteristic polynomials of Boolean functions 👍 👎
• A combinatorial characterization of Boolean algebras 👍 👎
• Numerical computation of characteristic polynomials of Boolean functions and its applications 👍 👎
• Characteristic polynomials and spectra of Boolean graphs 👍 👎
• Character analogue of the Boole summation formula with applications 👍 👎

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4835862)