  To test incomplete search algorithms for constraint satisfaction problems
such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances.
A simple way to do this is to choose a random truth assignment A, and then
choose clauses randomly from among those satisfied by A. However, this method
tends to produce easy problems, since the majority of literals point toward the
``hidden'' assignment A. Last year, Achlioptas, Jia and Moore proposed a
problem generator that cancels this effect by hiding both A and its complement.
While the resulting formulas appear to be just as hard for DPLL algorithms as
random 3-SAT formulas with no hidden assignment, they can be solved by WalkSAT
in only polynomial time. Here we propose a 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.
