Комбинаторный взрыв числа кандидатов
Любую минимальную по монотонному функционалу ДНФ можно искать среди тупиковых форм. Однако это ещё не делает перебор практичным. Лемма 8.1 строит функции от n≥4 переменных, имеющие \(5^{2^{n-4}}\) тупиковых и \(2^{2^{n-4}}\) минимальных ДНФ. Значит, сама выдача или перебор всех кандидатов может быть огромной.1
Размер сокращённой ДНФ и таблицы Квайна
Второй источник сложности — размер исходного пространства простых импликант. Для максимальной длины сокращённой ДНФ в курсе получена нижняя оценка
\(\lambda_{\text{сокр}}(n)\ge c\cdot 3^n/n\)
с некоторой положительной константой c. Таблица Квайна имеет по строке на каждую простую импликанту, поэтому её размер также может расти очень быстро.1
Связь с вычислительной сложностью
В лекциях приводится следующий аргумент. Проблема выполнимости КНФ относится к NP-полным. Если по КНФ построить сокращённую ДНФ реализуемой функции, то по наличию ненулевых членов можно решить вопрос о выполнимости. Поэтому уже этап перехода от КНФ к полной системе простых импликант является алгоритмически трудным.1
Ограничения локальных методов
Ю. И. Журавлёв предложил локальные алгоритмы, в которых решение о конъюнкции зависит от окрестности ограниченного порядка в сокращённой ДНФ. Для некоторых задач тупиковости достаточно малых окрестностей, но для принадлежности минимальным ДНФ ситуация хуже. В лекционном курсе показано, что в общем случае различение может требовать окрестности порядка n−3, а в более общей формулировке для любого фиксированного r существуют функции, где локальный алгоритм индекса r не способен решить эту задачу.1, 2
Эти результаты описывают разные источники трудности. Их не следует сводить к одному утверждению «минимизация ДНФ NP-полна»: курс отдельно рассматривает размер представления, число решений, классическую вычислительную сложность и локальность алгоритмов.