The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
From MaRDI portal
Publication:5901484
DOI10.1007/11786986_31zbMath1201.03023OpenAlexW1574333603MaRDI QIDQ5901484
Elitza Maneva, Parikshit Gopalan, Christos H. Papadimitriou, Phokion G. Kolaitis
Publication date: 12 March 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11786986_31
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)
Related Items
Ground State Connectivity of Local Hamiltonians, Reconfiguration of List Edge-Colorings in a Graph, On the Boolean connectivity problem for Horn relations, The connectivity of Boolean satisfiability: dichotomies for formulas and circuits, Finding Paths between Graph Colourings: Computational Complexity and Possible Distances, On the freezing of variables in random constraint satisfaction problems, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
