Random 2-SAT: Results and problems
From MaRDI portal
Publication:5958804
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)
Related Items (15)
A sharp threshold for a random constraint satisfaction problem ⋮ On the concentration of the number of solutions of random satisfiability formulas ⋮ Unnamed Item ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ Exact enumeration of satisfiable 2-SAT formulae ⋮ Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities ⋮ The cook-book approach to the differential equation method ⋮ 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} ⋮ Unnamed Item ⋮ Exact location of the phase transition for random (1,2)-QSAT ⋮ Unnamed Item ⋮ Unnamed Item
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
This page was built for publication: Random 2-SAT: Results and problems
