14
правок
Изменения
→Доказательство принадлежности классу NPH
# Для узла с меткой '''И''' соответствующая КНФ получается как конъюнкция ('''И''') всех дизъюнктов двух подформул <tex> \alpha </tex> и <tex> \beta </tex>.
# Для узла с меткой '''ИЛИ''' нужно ввести новую переменную. Добавляем ее во все дизъюнкты левого операнда <tex> \alpha </tex> и ее отрицание во все дизъюнкты правого операнда <tex> \beta </tex>. Можно заметить, что формула <tex> \alpha \vee \beta </tex> выполнима тогда и только тогда, когда выполнима <tex> (\alpha \vee y) \wedge (\beta \vee \neg y) </tex>, где <tex> y </tex> - новая переменная.
Новая формула увеличивается не более, чем на количество листьев в поддереве, а значит максимальное время работы алгоритма можно представить как ''(число листьев) * (число вершин)'', что соответствует оценке <tex> O(|\phi|^2) </tex>.
