Локальный поиск: поиск выполняющего набора в шаре радиуса \( r \) за \( O^*(3^r) \); оценки \( O^*(3^{n/2}) \) и \( O^*(1.5^n) \) с помощью покрытия шарами радиуса \( n/2 \) и \( n/4 \).

Литература: Uwe Schöning: A Probabilistic Algorithm for \( k \)-SAT and Constraint Satisfaction Problems. FOCS 1999: 410-414. [official, PDF] Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning: A deterministic \( (2-2/(k+1))^n \) algorithm for \( k \)-SAT based on local search. Theor. Comput. Sci. 289(1): 69-83 (2002). [official, PS]