We show that for k 5 , the PPSZ algorithm for k -SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every k 5 , there is a strictly increasing function f : [ 0 1 ] R with f (0) = 0 that has the following property. If F is a k -CNF formula over n variables and sat ( F ) = 2 n solutions, then PPSZ finds a satisfying assignment with probability at least 2 − c k n − o ( n )+ f ( ) n . Here, 2 − c k n − o ( n ) is the success probability proved by Paturi, Pudlak, Saks, and Zane for k -CNF formulas with a unique satisfying assignment.

Our proof rests on a combinatorial lemma: given a set S 0 1 n , we can partition 0 1 n into subcubes such that each subcube B contains exactly one element of S . Such a partition induces a distribution on itself, via Pr [ B ] = B 2 n for each B . We are interested in partitions that induce a distribution of high entropy. We show that, in a certain sense, the worst case ( min S : S = s max H ( ) ) is achieved if S is a Hamming ball. This lemma implies that every set S of exponential size allows a partition of linear entropy. This in turn leads to an exponential improvement of the success probability of PPSZ.