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

Simple item page
dc.creatorHajiaghayi, MohammadTaghi
dc.creatorSorkin, Gregory B.
dc.date2003-10-13
dc.date2003-10-22
dc.date.accessioned2026-07-07T05:01:52Z
dc.date.available2026-07-07T05:01:52Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/math/0310193
dc.identifierhttp://arxiv.org/abs/math/0310193
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/68838
dc.subjectCombinatorics
dc.subjectDiscrete Mathematics
dc.subjectProbability
dc.titleThe Satisfiability Threshold of Random 3-SAT Is at Least 3.52
dc.typetext

Files

Collections

arXiv