Локальный поиск: поиск выполняющего набора в шаре радиуса $ 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]