Typical random 3-SAT formulae and the satisfiability threshold

Simple item page
dc.creatorDubois, Olivier
dc.creatorBoufkhad, Yacine
dc.creatorMandler, Jacques
dc.date2002-11-26
dc.date.accessioned2026-07-07T03:19:03Z
dc.date.available2026-07-07T03:19:03Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/cs/0211036
dc.identifierhttp://arxiv.org/abs/cs/0211036
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31358
dc.subjectDiscrete Mathematics
dc.subjectComputational Complexity
dc.subjectG.2.1
dc.titleTypical random 3-SAT formulae and the satisfiability threshold
dc.typetext

Files

Collections

arXiv