Exact enumeration of satisfiable 2-SAT formulae

DOI10.5070/C63261985MaRDI QIDQ6138912OpenAlexFDO

Authors Sergey Dovgal, Elie de Panafieu, Vlady Ravelomanana

Publication date 16 December 2023

Published in Combinatorial Theory (Search for Journal in Brave)

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

zbMATH Keywords

generating functionsphase transitionsexact enumerationrandom graphssatisfiabilitystrongly connected components2-CNF

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Exact enumeration problems, generating functions (05A15)

Abstract: We obtain exact expressions counting the satisfiable 2-SAT formulae and describe the structure of associated implication digraphs. Our approach is based on generating function manipulations. To reflect the combinatorial specificities of the implication digraphs, we introduce a new kind of generating function, the Implication generating function, inspired by the Graphic generating function used in digraph enumeration. Using the underlying recurrences, we make accurate numerical predictions of the phase transition curve of the 2-SAT problem inside the critical window. We expect these exact formulae to be amenable to rigorous asymptotic analysis using complex analytic tools, leading to a more detailed picture of the 2-SAT phase transition in the future.

Recommendations

• The number of satisfying assignments of random 2‐SAT formulas
• scientific article; zbMATH DE number 2090009
• The number of 2-SAT functions
• The scaling window of the 2-SAT transition
• Rigorous results for random (\(2+p)\)-SAT

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3458676 (Why is no real title available?)
• scientific article; zbMATH DE number 3585466 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 473229 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 3409391 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• scientific article; zbMATH DE number 7651064 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A threshold for unsatisfiability
• Airy phenomena and analytic combinatorics of connected graphs
• An Asymptotic Expansion for the Coefficients of Some Formal Power Series
• Analytic combinatorics
• Analytic combinatorics of connected graphs
• Counting directed acyclic and elementary digraphs
• Enumerative applications of a decomposition for graphs and digraphs
• How frequently is a system of 2-linear Boolean equations solvable?
• On Some Features of the Structure of a Random Graph Near a Critical Point
• Paths in graphs
• Proof of the satisfiability conjecture for large \(k\)
• Random 2 XORSAT phase transition
• Random 2-SAT: Results and problems
• Random MAX SAT, random MAX CUT, and their phase transitions
• Some optimal inapproximability results
• Some simplified NP-complete graph problems
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• The Number of Strong Digraphs
• The asymptotic \(k\)-SAT threshold
• The birth of the giant component
• The complexity of theorem-proving procedures
• The continuum limit of critical random graphs
• The critical behavior of random digraphs
• The number of connected sparsely edged graphs
• The phase transition in the evolution of random digraphs
• The probabilistic method
• The scaling window of the 2-SAT transition
• The transitive closure of a random digraph
• Threshold functions for small subgraphs in simple graphs and multigraphs
• Une théorie combinatoire des séries formelles

Cited in

(1)

• An enumerative algorithm for \#2SAT

This page was built for publication: Exact enumeration of satisfiable 2-SAT formulae

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