LIPIcs.FSTTCS.2008.1750.pdf
- Filesize: 470 kB
- 12 pages
Document
A new upper bound for 3-SAT
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2008-12-05
Cite AsGet BibTex
Josep Diaz, Lefteris Kirousis, Dieter Mitsche, and Xavier Perez-Gimenez. A new upper bound for 3-SAT. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 163-174, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1750
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1750
Abstract
We show that a randomly chosen
$3$-CNF formula over $n$ variables with clauses-to-variables
ratio at least $4.4898$ is asymptotically almost surely unsatisfiable.
The previous best such bound,
due to Dubois in 1999, was $4.506$.
The first such bound, independently
discovered by many groups of researchers since 1983,
was $5.19$. Several decreasing values between
$5.19$ and $4.506$ were published in the years between.
The probabilistic techniques we use for the proof are, we believe, of independent interest.
Keywords
- Satisfiability
- 3-SAT
- random
- threshold
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads