On computing Boolean connectives of characteristic functions

DOI10.1007/BF01303054MaRDI QIDQ4835862zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

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

Cites work

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

Cited in

(25)

• The computational complexity of ideal semantics
• Numerical computation of characteristic polynomials of Boolean functions and its applications
• Completeness results for graph isomorphism.
• Trading properties and Alexandrov kernels for Boolean functions
• Commutative queries
• Bounded queries, approximations, and the Boolean hierarchy
• Parameterized random complexity
• Two queries
• Complexity of stability
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Characterization of Boolean valued star and mega lattice functions
• 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
• Lower bounds for kernelizations and other preprocessing procedures
• scientific article; zbMATH DE number 493087 (Why is no real title available?)
• Relativized logspace and generalized quantifiers over finite ordered structures
• Character analogue of the Boole summation formula with applications
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Lower bounds for kernelizations and other preprocessing procedures
• The 1-Versus-2 Queries Problem Revisited
• Approximate evaluations of characteristic polynomials of Boolean functions
• Complexity of Stability.
• Intersection suffices for Boolean hierarchy equivalence
• Characteristics of multiple viewpoints in abstract argumentation
• The 1-versus-2 queries problem revisited

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)