The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits

DOI10.1007/978-3-319-06686-8_27MaRDI QIDQ4981174zbMATH OpenOpenAlexFDO

Authors K. Schwerdtfeger

Publication date 24 June 2014

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-06686-8_27

Mathematics Subject Classification ID

Classical propositional logic (03B05) Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Recommendations

• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• A computational trichotomy for connectivity of Boolean satisfiability
• On the structure of Boolean satisfiability
• ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY
• On the structure of solution-graphs for Boolean formulas
• Bridging constraint satisfaction and Boolean satisfiability
• On the Boolean connectivity problem for Horn relations
• On the Boolean Connectivity Problem for Horn Relations

Cited in

(11)

• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• On the structure of solution-graphs for Boolean formulas
• Using Flexibility in P-Circuits by Boolean Relations
• A computational trichotomy for connectivity of Boolean satisfiability
• On the Boolean Connectivity Problem for Horn Relations
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Homomorphism reconfiguration via homotopy
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On the Boolean connectivity problem for Horn relations
• An exact algorithm for the Boolean connectivity problem for k-CNF

This page was built for publication: The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits

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