Теоретический семинар (осень 2013)

05.09.2013 (Сергей Савинов) Алгоритм для задачи выполнимости формулы

Рассказывается верхняя оценка O(2^{0.23248 L) в худшем случае для задачи выполнимости формулы над базисом {конъюнкция, дизъюнкция, отрицание}, где L - размер формулы.