License: 
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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1750/
Diaz, Josep ;
Kirousis, Lefteris ;
Mitsche, Dieter ;
Perez-Gimenez, Xavier
A new upper bound for 3-SAT
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 |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
05.12.2008 |
