Single-solution Random 3-SAT Instances

2005/04/25 by Marko Znidaric, Znidaric, Marko
Computer Science · #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.AI #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.cs/0504101

18 pages, 9 figures; considerable revision

arxiv created 2005/08/18 · arxiv updated 2009/12/01

Abstract

We 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.

Related

• On the Regularity of Random 2-SAT and 3-SAT
• On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas
• Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints
• Symbiosis of Search and Heuristics for Random 3-SAT
• The Satisfiability Threshold of Random 3-SAT Is at Least 3.52