DPLL-алгоритмы, основные идеи метода расщепления, вектор и число расщепления. \( O^*(2^{2n/3}) \) для задачи 3-выполнимости одновыполнимой формулы через расщепление относительно случайной перестановки. Запоминание дизъюнктов: решение задачи выполнимости на формулах константной плотности за \( O^*((2-c)^n) \). Комбинированные меры сложности, measure and conquer: \( O^*(2^{m/5.5}) \)для задачи максимальной 2-выполнимости.

Литература:
Timon Hertli: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. FOCS 2011: 277-284
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: An improved exponential-time algorithm for k-SAT. J. ACM 52(3): 337-364 (2005)
Alexander S. Kulikov, Konstantin Kutzkov: New Bounds for MAX-SAT by Clause Learning. CSR 2007: 194-204
Arist Kojevnikov, Alexander S. Kulikov: A new approach to proving upper bounds for MAX-2-SAT. SODA 2006: 11-17