Комбинаторный взрыв числа кандидатов
Любую минимальную по монотонному функционалу ДНФ можно искать среди тупиковых форм. Однако это ещё не делает перебор практичным. Лемма 8.1 строит функции от \(n\ge 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-полна»: курс отдельно рассматривает размер представления, число решений, классическую вычислительную сложность и локальность алгоритмов.