Article: Hiding Satisfying Assignments: Two are Better than One

Skip to first unread message

Nov 10, 2005, 8:01:42 PM11/10/05
JAIR is pleased to announce the publication of the following article:

Achlioptas, D., Jia, H. and Moore, C. (2005)
"Hiding Satisfying Assignments: Two are Better than One",
Volume 24, pages 623-639.

For quick access via your WWW browser, use this URL:

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, for a number of different
algorithms, A acts as a stronger and stronger attractor as the
formula's density increases. 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 compliment 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.

The article is available via:

-- (also see

-- World Wide Web: The URL for our World Wide Web server is
For direct access to this article and related files try:

-- Anonymous FTP from Carnegie-Mellon University (USA):
The compressed PostScript file is named

For more information about JAIR, visit our WWW or FTP sites, or

Steven Minton
JAIR Managing Editor

Reply all
Reply to author
0 new messages