A new upper bound for 3-SAT

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We show that a randomly chosen 3-CNF formula over n variables with clauses-to-variables ratio at least 4.4898 is, as n grows large, 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.
20 pages

Keywords

Discrete Mathematics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/165555

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0807.3600
 http://arxiv.org/abs/0807.3600

Collections

arXiv