Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2008.1750
URN: urn:nbn:de:0030-drops-17507
URL: https://drops.dagstuhl.de/opus/volltexte/2008/1750/
Diaz, Josep ; Kirousis, Lefteris ; Mitsche, Dieter ; Perez-Gimenez, Xavier
A new upper bound for 3-SAT
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{diaz_et_al:LIPIcs:2008:1750,
author = {Josep Diaz and Lefteris Kirousis and Dieter Mitsche and Xavier Perez-Gimenez},
title = {{A new upper bound for 3-SAT}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {163--174},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-08-8},
ISSN = {1868-8969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1750},
URN = {urn:nbn:de:0030-drops-17507},
doi = {10.4230/LIPIcs.FSTTCS.2008.1750},
annote = {Keywords: Satisfiability, 3-SAT, random, threshold}
}
| Keywords: | Satisfiability, 3-SAT, random, threshold | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science | |
| Issue date: | 2008 | |
| Date of publication: | 05.12.2008 |
