Bounding the unsatisfiability threshold of random 3-SAT
From MaRDI portal
Publication:4511484
DOI<103::AID-RSA2>3.0.CO;2-P 10.1002/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-PzbMath0958.03028OpenAlexW2132240307MaRDI QIDQ4511484
Yannis C. Stamatiou, Svante Janson, Malvina G. Vamvakari
Publication date: 6 February 2001
Full work available at URL: https://doi.org/10.1002/1098-2418(200009)17:2<103::aid-rsa2>3.0.co;2-p
generating functionsstatistical physicsspin systemGaussian coefficientsRogers-Szegö polynomialsrandom 3-SATsatisfiability thresholdunsatisfiability threshold
Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05)
Related Items
Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT, A sharp threshold for a random constraint satisfaction problem, A sharp threshold in proof complexity yields lower bounds for satisfiability search, On threshold properties of \(k\)-SAT: An additive viewpoint, The unsatisfiability threshold revisited, Phase transition in a random NK landscape model, The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘), Unnamed Item, On good algorithms for determining unsatisfiability of propositional formulas, On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT, The scaling window of the 2-SAT transition, On the satisfiability threshold and clustering of solutions of random 3-SAT formulas, An asymptotic expansion for theq-binomial series using singularity analysis for generating functions, Sharp thresholds for constraint satisfaction problems and homomorphisms, Rigorous results for random (\(2+p)\)-SAT, Upper bounds on the satisfiability threshold, When does the giant component bring unsatisfiability?, Selecting Complementary Pairs of Literals, An Empirical Study of MAX-2-SAT Phase Transitions
Cites Work
