Single-solution Random 3-SAT Instances

Details Single-solution Random 3-SAT Instances Single-solution Random 3-SAT Instances

2005-04-25

arxiv.org/abs/cs/0504101v2

Computer Science

Artificial Intelligence

18 pages, 9 figures; considerable revision

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Single-solution Random 3-SAT Instances does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Single-solution Random 3-SAT Instances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single-solution Random 3-SAT Instances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-468301