Title: Constructing Hard Satisfiable SAT formulas

Speaker: Dr. Haixia Jia, UNM

Date/Time: Tuesday, February 12, 2008, from 1:00 to 2:00 pm

Location: CSRI Building, Room 279 (Sandia NM)

Brief Abstract: The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances are k-CNF formulas whose clauses are chosen uniformly at random among all clauses satisfying some randomly chosen truth assignment A. Unfortunately, instances generated in this manner are relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, as the number of clauses is increased, A acts as a stronger and stronger attractor. Motivated by recent results on the geometry of the space of solutions for random k-SAT and NAE-k-SAT instances, we propose a very simple twist on this model that greatly increases the hardness of the resulting formulas. 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 the 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 an algorithm to "feel" (and find) either one. We give theoretical and experimental evidence supporting this assertion. We then propose another new method to cancel the attraction to A, by choosing a clause with t > 0 literals satisfied by A with probability proportional to q^t for some q < 1. By varying q, we can generate formulas whose variables have no bias, i.e., which are equally likely to be true or false; we can even cause the formula to "deceptively" point away from A. We present theoretical and experimental results suggesting that these formulas are exponentially hard both for DPLL algorithms and for incomplete algorithms such as WalkSAT.

CSRI POC: Mark D. Rintoul, (505) 844-9592