Random 2-SAT: Results and problems

DOI10.1016/S0304-3975(01)00156-6zbMath0983.68080MaRDI QIDQ5958804

Wenceslas Fernandez de la Vega

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

phase transition; satisfiability; random 2-CNF formulas

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Exact location of the phase transition for random (1,2)-QSAT, Satisfiability threshold for power law random 2-SAT in configuration model, Rigorous results for random (\(2+p)\)-SAT, Lower bounds for random 3-SAT via differential equations, Satisfiability threshold for random regular \textsc{nae-sat}, The number of satisfying assignments of random 2‐SAT formulas, Exact enumeration of satisfiable 2-SAT formulae, The cook-book approach to the differential equation method, A sharp threshold for a random constraint satisfaction problem, Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities, On the concentration of the number of solutions of random satisfiability formulas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• 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
• Random 2-SAT and unsatisfiability
• Weighted sums of certain dependent random variables
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Entropy of theK-Satisfiability Problem
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Tricritical points in random combinatorics: the -SAT case
• A threshold for unsatisfiability
• The giant component threshold for random regular graphs with edge faults H. Prodinger