Computer Science – Artificial Intelligence
Scientific paper
2005-03-20
Computer Science
Artificial Intelligence
Preliminary version appeared in AAAI 2004
Scientific paper
The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-SAT formulas whose clauses are chosen uniformly from among all clauses satisfying some randomly chosen truth assignment A. Unfortunately, instances generated in this manner tend to be relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, as the formula's density increases, for a number of different algorithms, A acts as a stronger and stronger attractor. Motivated by recent results on the geometry of the space of satisfying truth assignments of random k-SAT and NAE-k-SAT formulas, we introduce a simple twist on this basic model, which appears to dramatically increase its hardness. Namely, in addition to forbidding the clauses violated by the hidden assignment A, we also forbid the clauses violated by its complement, so that both A and complement of A are satisfying. It appears that under this "symmetrization'' the effects of the two attractors largely cancel out, making it much harder for algorithms to find any truth assignment. We give theoretical and experimental evidence supporting this assertion.
Achlioptas Dimitris
Jia Haixia
Moore Cristopher
No associations
LandOfFree
Hiding Satisfying Assignments: Two are Better than One 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 Hiding Satisfying Assignments: Two are Better than One, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hiding Satisfying Assignments: Two are Better than One will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-261651