A computational trichotomy for connectivity of Boolean satisfiability

MaRDI QIDQ3194807zbMATH OpenFDO

Authors K. Schwerdtfeger

Publication date 20 October 2015

Full work available at URL https://arxiv.org/abs/1312.4524

zbMATH Keywords

Boolean CSPsBoolean satisfiabilitycomputational complexitydichotomy theoremsgraph connectivityPSPACE-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
• 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
• An exact algorithm for the Boolean connectivity problem for k-CNF

Cited in

(17)

• Reconfiguration on nowhere dense graph classes
• Introduction to reconfiguration
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• Solution-Graphs of Boolean Formulas and Isomorphism
• On the structure of solution-graphs for Boolean formulas
• Shortest reconfiguration paths in the solution space of Boolean formulas
• On the Boolean Connectivity Problem for Horn Relations
• scientific article; zbMATH DE number 6861969 (Why is no real title available?)
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
• Solution-Graphs of Boolean Formulas and Isomorphism1
• Homomorphism reconfiguration via homotopy
• Shortest reconfiguration paths in the solution space of Boolean formulas
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On connectedness of solutions to integer linear systems
• Reconfiguring homomorphisms to reflexive graphs via a simple reduction
• Reconfiguration of digraph homomorphisms

This page was built for publication: A computational trichotomy for connectivity of Boolean satisfiability

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