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)
68Q25: Analysis of algorithms and problem complexity
Related Items
Unnamed Item, Unnamed Item, Exact location of the phase transition for random (1,2)-QSAT, 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 cook-book approach to the differential equation method, A sharp threshold for a random constraint satisfaction problem, 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
