On computing Boolean connectives of characteristic functions
From MaRDI portal
Publication:4835862
DOI10.1007/BF01303054zbMATH Open0827.68065OpenAlexW1991109776WikidataQ59795820 ScholiaQ59795820MaRDI QIDQ4835862FDOQ4835862
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
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
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (25)
- Commutative queries
- Lower bounds for kernelizations and other preprocessing procedures
- 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
- 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
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)
