The Satisfiability Threshold of Random 3-SAT Is at Least 3.52

Hajiaghayi, MohammadTaghi; Sorkin, Gregory B.

The Satisfiability Threshold of Random 3-SAT Is at Least 3.52

Authors

Description

We prove that a random 3-SAT instance with clause-to-variable density less than 3.52 is satisfiable with high probability. The proof comes through an algorithm which selects (and sets) a variable depending on its degree and that of its complement.

Keywords

Combinatorics, Discrete Mathematics, Probability

URI

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

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0310193
http://arxiv.org/abs/math/0310193

Collections

arXiv

Full item page

The Satisfiability Threshold of Random 3-SAT Is at Least 3.52

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Keywords

Citation

URI

Consulte el texto completo en el siguiente enlace:

Collections