The connectivity of Boolean satisfiability: dichotomies for formulas and circuits

DOI10.1007/s00224-015-9663-zzbMath1378.68093arXiv1312.6679OpenAlexW2787312740MaRDI QIDQ2411031

Konrad W. Schwerdtfeger

Publication date: 20 October 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

graph connectivityBoolean satisfiabilityPSPACE-completenessBoolean circuitsdichotomy theoremsPost's lattice

Mathematics Subject Classification ID

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

Uses Software

• QuteSAT

Cites Work

• On the applicability of Post's lattice
• On the complexity of reconfiguration problems
• Structure identification of Boolean relations and plain bases for co-clones
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• On connected Boolean functions
• Finding paths between 3-colorings
• Shortest Paths between Shortest Paths and Independent Sets
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• A new look at survey propagation and its generalizations
• Enumerating All Solutions for Constraint Satisfaction Problems
• On the Boolean Connectivity Problem for Horn Relations
• Satisfiability problems for propositional calculi
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• On the solution-space geometry of random constraint satisfaction problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Unnamed Item
• Unnamed Item

This page was built for publication: The connectivity of Boolean satisfiability: dichotomies for formulas and circuits