A new upper bound for 3-SAT

DOI10.4230/LIPICS.FSTTCS.2008.1750MaRDI QIDQ3165956zbMATH OpenOpenAlexFDO

Authors L. M. Kirousis, D. Mitsche, Xavier Pérez-Giménez, J. Díaz

Publication date 19 October 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_58d1.html

zbMATH Keywords

3-SATrandomsatisfiabilitythreshold

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• On the satisfiability threshold of formulas with three literals per clause
• scientific article; zbMATH DE number 1114008
• Bounding the unsatisfiability threshold of random 3-SAT
• On Random 3-sat
• The unsatisfiability threshold revisited

Cited in

(15)

• New methods for 3-SAT decision and worst-case analysis
• On the satisfiability threshold of formulas with three literals per clause
• New upper bound for the \#3-SAT problem
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• scientific article; zbMATH DE number 1113996 (Why is no real title available?)
• scientific article; zbMATH DE number 1114008 (Why is no real title available?)
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• scientific article; zbMATH DE number 7029312 (Why is no real title available?)
• On Random 3-sat
• Size, cost and capacity: a semantic technique for hard random QBFs
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• A new upper bound for random (2 + p)-SAT by flipping two variables
• Upper bounds on the satisfiability threshold
• An upper (lower) bound for Max (Min) CSP

This page was built for publication: A new upper bound for 3-SAT

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