The number of satisfying assignments of random 2‐SAT formulas

DOI10.1002/rsa.20993zbMath1522.68375MaRDI QIDQ6074640

No author found.

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

zbMATH Keywords

satisfiability problembelief propagation2-SAT

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)

Related Items (2)

Counting Solutions to Random CNF Formulas ⋮ Belief propagation on the random \(k\)-SAT model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spin glass models from the point of view of spin distributions
• Combinatorics and complexity of partition functions
• A threshold for unsatisfiability
• On the replica symmetric solution of the \(K\)-sat model
• The asymptotic \(k\)-SAT threshold
• Ising models on locally tree-like graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Length of prime implicants and number of solutions of random CNF formulae
• The 3-XORSAT threshold.
• Information-theoretic thresholds from the cavity method
• Bounds for diluted mean-fields spin glass models
• Replica bounds for optimization problems and diluted spin systems
• Broken replica symmetry bounds in the mean field spin glass model
• The satisfiability threshold for random linear equations
• Factor models on locally tree-like graphs
• Random 2-SAT with prescribed literal degrees
• The scaling window of the 2-SAT transition
• On the concentration of the number of solutions of random satisfiability formulas
• Proof of the Satisfiability Conjecture for Large k
• The Number of Satisfying Assignments of Random Regulark-SAT Formulas
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Information, Physics, and Computation
• The Evolution of Random Graphs
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• The Complexity of Enumeration and Reliability Problems
• Component behavior near the critical point of the random graph process
• Entropy of theK-Satisfiability Problem
• Random MAX SAT, random MAX CUT, and their phase transitions
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The Monge-Kantorovich problem: achievements, connections, and perspectives
• The replica symmetric phase of random constraint satisfaction problems
• On the Number of Solutions in Random Graphk-Colouring
• The Satisfiability Threshold fork-XORSAT
• Gibbs states and the set of solutions of random constraint satisfaction problems
• The high temperature case for the random \(K\)-sat problem
• Random 2-SAT: Results and problems
• Satisfiability threshold for random regular \textsc{nae-sat}

This page was built for publication: The number of satisfying assignments of random 2‐SAT formulas