Solution-Graphs of Boolean Formulas and Isomorphism1

DOI10.3233/SAT190113MaRDI QIDQ5015600zbMATH OpenOpenAlexFDO

Authors Patrick Scharpfenecker, Jacobo Torán

Publication date 9 December 2021

Published in Journal on Satisfiability, Boolean Modeling and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/sat190113

zbMATH Keywords

countingisomorphismpartial cubesolution-graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational aspects of satisfiability (68R07)

Recommendations

• Solution-Graphs of Boolean Formulas and Isomorphism
• On the structure of solution-graphs for Boolean formulas
• scientific article; zbMATH DE number 1948177
• Hypergraph isomorphism and structural equivalence of Boolean functions
• Proof graphs for parameterised Boolean equation systems
• Analysis of Boolean equation systems through structure graphs
• scientific article; zbMATH DE number 3952822
• Polynomial equivalence of the problems ``predicate formulas isomorphism and graph isomorphism

Cites work

• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• A computational trichotomy for connectivity of Boolean satisfiability
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Completeness results for graph isomorphism.
• Embedding Topological Median Algebras in Products of Dendrons
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism is low for PP
• Graphs and cubes
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Metric graph theory and geometry: a survey
• On the interpolation between product-based message passing heuristics for SAT
• On the power of deterministic reductions to C=P
• On the solution-space geometry of random constraint satisfaction problems
• On the structure of solution-graphs for Boolean formulas
• Parity separation: a scientifically proven method for permanent weight loss
• Solution-Graphs of Boolean Formulas and Isomorphism
• The Complexity of Enumeration and Reliability Problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent
• The complexity of satisfiability problems

Cited in

(3)

• Solution-Graphs of Boolean Formulas and Isomorphism
• On the structure of solution-graphs for Boolean formulas
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)

This page was built for publication: Solution-Graphs of Boolean Formulas and Isomorphism1

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