Подсчет числа нулевых наборов и проблема выполнимости

Abstract

Во втором издании опущены все те выкладки из первого , которые не касаются алгоритма проверки выполнимости конъюнктивной нормально формы (КНФ), основанного на разбиении одного ее подмножества элементарных дизъюнкций (ЭД). Правда, в этом издании это разбиение осуществляется для 3-КНФ, где каждая ЭД содержит литералы только с отрицаниями или только без отрицаний (названной разделимой). Для каждой разделимой 3-КНФ эффективно находится выполняющий набор, если он существует. Следовательно, NP=P. For every special 3-CNF we efficiently find its executing assembly if it ex-ists. This algorithm refutes the wellknown hypothesis: NP≠P.