Typical random 3-SAT formulae and the satisfiability threshold

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We present a new structural (or syntatic) approach for estimating the satisfiability threshold of random 3-SAT formulae. We show its efficiency in obtaining a jump from the previous upper bounds, lowering them to 4.506. The method combines well with other techniques, and also applies to other problems, such as the 3-colourability of random graphs.

Keywords

Discrete Mathematics, Computational Complexity, G.2.1

Citation

URI

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

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0211036
 http://arxiv.org/abs/cs/0211036

Collections

arXiv