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

Gaussian coefficientsgenerating functionsrandom 3-SATRogers-Szegö polynomialssatisfiability thresholdspin systemstatistical physicsunsatisfiability threshold

Mathematics Subject Classification ID

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

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

(36)

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

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)