Random 2-SAT: Results and problems
In the random 2-SAT problem, we are given a set \(C\) of \(m\) disjunctions of two literals chosen at random within the \((\frac{2n}{2})\) pairs of distinct literals coming from \(n\) logical variables. The basic problem is to find out for which values of the ratio \(\rho=m/n\) the disjunctions in \(C\) are almost surely simultaneously satisfiable (or almost surely not simultaneously satisfiable) as \(n\) tends to infinity. The purpose of this paper is to review the main steps in the solution of this problem, starting with the location of the asymptotic critical ratio around 8 years ago and ending with the recent almost complete solution due to Bollobás et al. Thus, this paper is not a review in the usual sense of the word, i.e., it does not include all the known results about random 2-SAT. We will also make a few comments concerning the behaviour of the number of satisfying assignments of random instances of 2-SAT below the critical ratio, a problem relevant to theoretical physics.
- 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
- 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
- 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)
