DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2008.1750

A new upper bound for 3-SAT

Authors: Josep Diaz, Lefteris Kirousis, Dieter Mitsche, and Xavier Perez-Gimenez

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{diaz_et_al:LIPIcs.FSTTCS.2008.1750,
  author =	{Diaz, Josep and Kirousis, Lefteris and Mitsche, Dieter and Perez-Gimenez, Xavier},
  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 =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1750},
  URN =		{urn:nbn:de:0030-drops-17507},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1750},
  annote =	{Keywords: Satisfiability, 3-SAT, random, threshold}
}

Search Results

Documents authored by Perez-Gimenez, Xavier

A new upper bound for 3-SAT

Abstract

Cite as

Thanks for your feedback!

Could not send message