Верхняя оценка $O(2^{0.16254n})$ для X3SAT: более простое доказательство

Задача точной 3-выполнимости (X3SAT) заключается в нахождении для булевой формулы в 3-КНФ набора истинностных значений, выполняющего ровно по одному литералу в каждом клозе. Хорошо известно, что задача X3SAT является NP-полной. В данной работе мы приводим алгоритм, решающий задачу X3SAT за время $O(2^{0.162536n})$, где $n$ – количество переменных. Приводимое нами доказательство этой оценки несколько проще доказательства Поршена, Рандерата и Шпекенмейера. Эти доказательства независимы (а алгоритмы слегка отличаются), хотя и основаны на одних и тех же идеях из доказательства предыдущей оценки $O(2^{0.186916n})$ тех же авторов. Библ. – 6 назв.