Bounding the unsatisfiability threshold of random 3-SAT

DOI10.1002/1098-2418(200009)17:2%3C103::AID-RSA2%3E3.0.CO;2-PzbMATH Open0958.03028OpenAlexW2132240307MaRDI QIDQ4511484FDOQ4511484

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

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

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)

Cites Work

• Title not available (Why is that?)

Cited In (35)

• Computer Science Logic
• Approximating the unsatisfiability threshold of random formulas (extended abstract)
• The unsatisfiability threshold revisited
• A new upper bound for 3-SAT
• Super solutions of random \((3 + p)\)-SAT
• A sharp threshold for a random constraint satisfaction problem
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• On good algorithms for determining unsatisfiability of propositional formulas
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• On the satisfiability threshold of formulas with three literals per clause
• An asymptotic expansion for theq-binomial series using singularity analysis for generating functions
• Title not available (Why is that?)
• On threshold properties of \(k\)-SAT: An additive viewpoint
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• Selecting Complementary Pairs of Literals
• When does the giant component bring unsatisfiability?
• The scaling window of the 2-SAT transition

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)