Random 2-SAT: Results and problems

DOI10.1016/S0304-3975(01)00156-6MaRDI QIDQ5958804zbMATH OpenFDO

Authors W. Fernandez de la Vega

Publication date 3 March 2002

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

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00156-6

zbMATH Keywords

phase transitionrandom 2-CNF formulassatisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Rigorous results for random (2+p)-SAT
• A remark on random 2-SAT
• Random 2-SAT and unsatisfiability
• The number of satisfying assignments of random 2‐SAT formulas
• Approximating highly satisfiable random 2-SAT
• Random 2-XORSAT at the Satisfiability Threshold
• scientific article; zbMATH DE number 2119678
• Random 2-SAT with prescribed literal degrees
• The satisfiability threshold for non-uniform random 2-SAT

Cites work

• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A threshold for unsatisfiability
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Entropy of theK-Satisfiability Problem
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1369842 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• Length of prime implicants and number of solutions of random CNF formulae
• On the Complexity of Timetable and Multicommodity Flow Problems
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Random 2-SAT and unsatisfiability
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• Tricritical points in random combinatorics: the -SAT case
• Weighted sums of certain dependent random variables

Cited in

(22)

• A sharp threshold for a random constraint satisfaction problem
• Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities
• Almost every 2-SAT function is unate
• Random 2-SAT with prescribed literal degrees
• On the concentration of the number of solutions of random satisfiability formulas
• scientific article; zbMATH DE number 5139164 (Why is no real title available?)
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• scientific article; zbMATH DE number 7029312 (Why is no real title available?)
• The cook-book approach to the differential equation method
• scientific article; zbMATH DE number 2119678 (Why is no real title available?)
• Size, cost and capacity: a semantic technique for hard random QBFs
• Bounds on the satisfiability threshold for power law distributed random SAT
• Exact location of the phase transition for random (1,2)-QSAT
• Random 2-SAT solution components and a fitness landscape
• scientific article; zbMATH DE number 3423964 (Why is no real title available?)
• 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
• On the chromatic number of random triangle-free graphs

This page was built for publication: Random 2-SAT: Results and problems

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