On Random 3-sat

DOI10.1017/S0963548300001590MaRDI QIDQ4862742zbMATH OpenOpenAlexFDO

Authors A. El Maftouhi, W. Fernandez de la Vega

Publication date 1 July 1996

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548300001590

zbMATH Keywords

satisfiability

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• A new upper bound for 3-SAT
• On the satisfiability threshold of formulas with three literals per clause
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Bounding the unsatisfiability threshold of random 3-SAT
• A remark on random 2-SAT

Cites work

• Central and local limit theorems applied to asymptotic enumeration
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem

Cited in

(16)

• The maximum length of prime implicates for instances of 3-SAT
• On good algorithms for determining unsatisfiability of propositional formulas
• Random 2-SAT and unsatisfiability
• A remark on random 2-SAT
• On the satisfiability threshold of formulas with three literals per clause
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• The scaling window of the 2-SAT transition
• 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
• Many hard examples for resolution
• Sharp thresholds of graph properties, and the k-sat problem
• Rigorous results for random (2+p)-SAT
• Upper bounds on the satisfiability threshold
• Number of models and satisfiability of sets of clauses
• On threshold properties of k-SAT: An additive viewpoint

This page was built for publication: On Random 3-sat

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