Single-solution Random 3-SAT Instances

Simple item page
dc.creatorZnidaric, Marko
dc.date2005-04-25
dc.date2005-08-18
dc.date.accessioned2026-07-07T03:22:55Z
dc.date.available2026-07-07T03:22:55Z
dc.descriptionWe study a class of random 3-SAT instances having exactly one solution. The properties of this ensemble considerably differ from those of a random 3-SAT ensemble. It is numerically shown that the running time of several complete and stochastic local search algorithms monotonically increases as the clause density is decreased. Therefore, there is no easy-hard-easy pattern of hardness as for standard random 3-SAT ensemble. Furthermore, the running time for short single-solution formulas increases with the problem size much faster than for random 3-SAT formulas from the phase transition region.
dc.description18 pages, 9 figures; considerable revision
dc.identifierhttps://arxiv.org/abs/cs/0504101
dc.identifierhttp://arxiv.org/abs/cs/0504101
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32744
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.titleSingle-solution Random 3-SAT Instances
dc.typetext

Files

Collections

arXiv