Bounding the unsatisfiability threshold of random 3-SAT

DOI10.1002/1098-2418(200009)17:2%3C103::AID-RSA2%3E3.0.CO;2-PMaRDI QIDQ4511484zbMATH OpenOpenAlexFDO

Authors Svante Janson, Yannis C. Stamatiou, Malvina Vamvakari

Publication date 6 February 2001

Full work available at URL https://doi.org/10.1002/1098-2418(200009)17:2%3C103::aid-rsa2%3E3.0.co;2-p

zbMATH Keywords

generating functionsspin systemstatistical physicsGaussian coefficientsrandom 3-SATsatisfiability thresholdRogers-Szegö polynomialsunsatisfiability threshold

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1445295
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• On the limit of branching rules for hard random unsatisfiable 3-SAT
• scientific article; zbMATH DE number 437557
• Lower bounds for random 3-SAT via differential equations
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• Non uniform selection of solutions for upper bounding the 3-SAT threshold
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem

Cited in

(35)

• The scaling window of the 2-SAT transition
• Computer Science Logic
• The unsatisfiability threshold revisited
• Approximating the unsatisfiability threshold of random formulas (extended abstract)
• Super solutions of random \((3 + p)\)-SAT
• A new upper bound for 3-SAT
• A sharp threshold for a random constraint satisfaction problem
• On good algorithms for determining unsatisfiability of propositional formulas
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• On the satisfiability threshold of formulas with three literals per clause
• On threshold properties of k-SAT: An additive viewpoint
• An asymptotic expansion for theq-binomial series using singularity analysis for generating functions
• scientific article; zbMATH DE number 2159650 (Why is no real title available?)
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• On the Lower Bounds of Random Max 3 and 4-SAT
• Upper bounds on the satisfiability threshold
• On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Tail bounds for occupancy and the satisfiability threshold conjecture
• The phase transition in exact cover
• Rigorous results for random (\(2+p)\)-SAT
• scientific article; zbMATH DE number 437557 (Why is no real title available?)
• Phase transition in a random NK landscape model
• Lower bounds for random 3-SAT via differential equations
• An Empirical Study of MAX-2-SAT Phase Transitions
• The unsatisfiability threshold revisited
• On Random 3-sat
• Non uniform selection of solutions for upper bounding the 3-SAT threshold
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• scientific article; zbMATH DE number 2044510 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• When does the giant component bring unsatisfiability?
• Selecting Complementary Pairs of Literals

This page was built for publication: Bounding the unsatisfiability threshold of random 3-SAT

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