Максимальный размер минимальной КНФ

[Tot]

Дано $n$ булевых переменных.
Рассматриваем задачу выполнимости булевой функции от этих $n$ переменных в форме КНФ.
КНФ минимальна, если в её записи используются переменные суммарно минимальное количество раз. Все известные алгоритмы точной минимизации, если правильно понимаю, экспоненциальны.
Поэтому возникает вопрос о максимальном размере минимальной КНФ на всём множестве булевых функций от $n$ переменных.
С одной стороны задача выполнимости КНФ NP-полная по теореме Кука. Стало быть по крайней мере минимальная КНФ должна проверяться за полиномиальное время от числа переменных, то есть иметь полиномиальный от переменных размер.
С другой стороны количество булевых функций от $n$ переменных равно $2^{2^n}$. Каждый дизъюнкт может быть записан как линейное неравенство с единичными коэффициентами. Если бы было равенство, то один дизъюнкт давал бы $2^n$ вариантов входящих переменных, а при неравенстве это число строго не больше. Поэтому найдётся такая КНФ, в которой $2^n/n$ дизъюнктов (линейная форма с единичными коэффициентами такой сложности), то есть размер минимальной КНФ экспоненциально зависит от количества переменных.
Полученное противоречие говорит о том, что где-то ошибаюсь.
Каков же максимальный размер минимальной КНФ?

[Xaositect]

Tot в сообщении #1109222 писал(а):

С одной стороны задача выполнимости КНФ NP-полная по теореме Кука. Стало быть по крайней мере минимальная КНФ должна проверяться за полиномиальное время от числа переменных, то есть иметь полиномиальный от переменных размер.

Не понимаю этого вывода. В задаче выполнимости КНФ является входом, то есть проверка должна идти за время, полиномиальное относительно размера ДНФ.

Tot в сообщении #1109222 писал(а):

С другой стороны количество булевых функций от $n$ переменных равно $2^{2^n}$. Каждый дизъюнкт может быть записан как линейное неравенство с единичными коэффициентами. Если бы было равенство, то один дизъюнкт давал бы $2^n$ вариантов входящих переменных, а при неравенстве это число строго не больше. Поэтому найдётся такая КНФ, в которой $2^n/n$ дизъюнктов (линейная форма с единичными коэффициентами такой сложности), то есть размер минимальной КНФ экспоненциально зависит от количества переменных.

Тут тоже не понимаю, откуда взялось $2^n/n$. Единственная минимальная КНФ у линейной функции --- это совершенная КНФ, у нее $2^{n-1}$ сомножителей.

[Tot]

Xaositect в сообщении #1109243 писал(а):

Не понимаю этого вывода. В задаче выполнимости КНФ является входом, то есть проверка должна идти за время, полиномиальное относительно размера ДНФ.

Задачу выполнимости понимаю следующим образом.
Дана произвольная булева функция на $n$ переменных в КНФ, то есть имеем конъюнкцию кучи дизъюнктов, в каждом из которых каждая переменная либо не содержится, либо содержится один раз с отрицанием или без. Пусть мы живём в мире Алгоритмика, у нас $NP=P$. Решатель задачи выполнимости нам нашёл набор значений наших переменных, при котором наша булева функция истинна. Стало быть можно этот набор подставить в КНФ и убедиться в истинности каждого дизъюнкта. Сколько этих дизъюнктов в исходной КНФ? Нам ведь нужно проверить их все. А если число дизъюнктов экспоненциально относительно количества переменных входной функции $n$. Проверка тоже станет экспоненциальной. Перевод КНФ в ДНФ тоже экспоненциален. Если правильно понял Ваше замечание, то проверка должна идти полиномиальное время относительно количества дизъюнктов в исходной КНФ.

[Xaositect]

Tot в сообщении #1109262 писал(а):

А если число дизъюнктов экспоненциально относительно количества переменных входной функции $n$. Проверка тоже станет экспоненциальной. Перевод КНФ в ДНФ тоже экспоненциален. Если правильно понял Ваше замечание, то проверка должна идти полиномиальное время относительно количества дизъюнктов в исходной КНФ.

Да, в определениях классов $P$ и $NP$ полином всегда от длины входа. В нашем случае длина входа - это не количество переменных, а длина записи КНФ.

[Tot]

Тогда такой пример для объяснения моих размышлений.
Возьмём две задачи на $n$ булевых переменных: задачу выполнимости и задачу суммы подмножества. Пусть это две записи одной и той же задачи, то есть вектор решений единственный и одинаковый. Обе задачи $NP$-полны, то есть существует возможность полиномиально перевести одну задачу в другую и обратно без добавления вспомогательных переменных. В мире Алгоритмика получили решение, у нас $n$ не допускает полный перебор. Проверяем. В задаче суммы подмножества складываем $n$ чисел, сложение - операция линейная, и получаем результат за $n^2$ операций. А что с проверкой КНФ? Проверка одного дизъюнкта линейна, а таких дизъюнктов пруд пруди, например $2^n/(\operatorname{const}n)$. Получается проверка, как и перевод, полиномиален, но лишь относительно размера входа, то есть только в теории. Задача одна в двух формах, а сложность проверки разная из-за разности размера входных данных одной и той же задачи.

[Tot]

Вывод из вышенаписанного такой.
Булева функция в КНФ может быть по числу дизъюнктов полиномиальной или экспоненциальной относительно числа переменных. Максимальный размер минимальной КНФ экспоненциален по этому параметру. Для конкретного ответа можно рассмотреть $n$-мерный куб Карно. В шахматном порядке нолики расположить или понадобится более хитрая конструкция с узором из пар ноликов, где следующая пара наполовину наложена на предыдущую и повёрнута относительно неё на 90 градусов, это не важно с точки зрения практики, так как результат будет экспоненциальным.
Если у КНФ реальной задачи дизъюнктов в небольшое количество раз большее, чем переменных, то повезло. Тогда можно на практике перевести её в любую другую $NP$-полную задачу с более компактным входом. В противном случае иногда могут помочь методы неточной минимизации.

Не совсем понятно, зачем в мире львиную долю усилий на практическое решение $NP$-полных задач тратят на решатели задачи выполнимости. Ежегодные соревнования, конференции и прочее. Да, выполнимость булевой функции - основная задача классической логики нулевого порядка, некоторое эталонное представление любой задачи в рамках этой логики, но и самый большой вход для решателя $NP$- полных задач. Было бы разумней, на мой взгляд, основные усилия сосредоточить на решении задачи программирования в ограничениях. Любая задача булевой логики легко записывается в таком виде. Затем программирование в ограничениях сводим к булевому программированию, а потом переходим к задаче суммы подмножества, как к задаче с самым коротким входом.

[Xaositect]

Все не так. В общем случае у двух $NP$-полных задач сводимость переводит входы одной задачи во входы другой задачи, у которых длины сравнимы (полиномиально связаны).

Если перейти от выполнимости к булеву линейному программированию и от него к subset sum, то в итоговом множестве будет столько же чисел, сколько было переменных в исходной КНФ, но зато длина каждого числа в битах будет порядка количества сомножителей в исходной КНФ, так что длина входа получится примерно такая же, как и у исходной задачи.

Если мы говорим о $P$ и $NP$, то нельзя забывать, что числа у нас не просто числа, а пишутся с помощью цифр и могут быть длинными.

[Tot]

И при этом задача суммы подмножества, полученная из КНФ с $n$ переменными и $l$ дизъюнктами, $l$ много больше $n$, почти всегда будет иметь то же количество решений по модулю $2^n$, что и без модуля.
Это можно сравнить с симплекс-методом в линейном программировании. Почти всегда полиномиален. Построение примера, где проявляется экспоненциальность метода, возможно, но алгоритмически сложно.
Может ли в таком случае исходная КНФ почти всегда быть минимизирована до КНФ c гораздо меньшим числом дизъюнктов?

[Tot]

Однако получение более короткой КНФ невозможно путём простого усечения числа дизъюнктов исходной, так как при получении задачи суммы подмножества из КНФ через булево программирование каждый дизъюнкт-неравенство влияет почти всегда на все биты каждого числа множества коэффициентов задачи subset sum.
Следовательно, такой приём не пройдёт даже теоретически, если в качестве исходной КНФ использовать задачу чёрного ящика без памяти с $n$ переменными, где $n$ - число входов плюс выходов.
Модель чёрного ящика точно получить можно лишь полным перебором таблицы истинности. "Почти всегда" в такой модели присутствует с вероятностью единица. Однако из вышенаписанного получается, что можно построить приближённую модель перебором полиномиального числа входов, а получение контрпримера к такой модели сделать вычислительно сложной задачей.
Получение приближённой КНФ из точной является экспоненциально сложной задачей, а вот путём построения приближённой модели чёрного ящика полиномиальной.

[Xaositect]

Tot в сообщении #1109410 писал(а):

И при этом задача суммы подмножества, полученная из КНФ с $n$ переменными и $l$ дизъюнктами, $l$ много больше $n$, почти всегда будет иметь то же количество решений по модулю $2^n$, что и без модуля.

В каком смысле почти всегда? Заметьте, мы говорим о случае, когда $l$ порядка $2^{O(n)}$ по длине, то есть порядка $2^{2^{O(n)}}$ по величине.

[Tot]

С Вашей оценкой размера согласен, но он не имеет значения, так как в задаче сумма подмножества все биты всех элементов этого множества никак не коррелируют друг с другом, являясь по сути случайными величинами с равномерным распределением, так как зависят лишь от наличия каждой переменной в каждом дизъюнкте и наличия у этой переменной знака отрицания. Поэтому применение модуля $2^n$ не должно вызвать появления большого количества лишних решений в среднем по всему массиву булевых функций от $n$ переменных.
Покажу эту мысль на примере из практики.
Возьмём задачу дискретного логарифма по простому модулю.
$a^x=Cp +y$. В прошлом веке она использовалась в криптографии, к тому же лет сорок уже болтается между $NP$ и $P$ классами, в общем пользуется популярностью, к тому же задача сильно нелинейна, что приводит к большому размеру КНФ.
Шесть лет назад была кандидатская на тему "КНФ представления для задач факторизации, дискретного логарифма...", там можно посмотреть оценки количества дизъюнктов. Правда от вспомогательных переменных для простоты там, если правильно помню, не избавлялись, но такая чистка количество дизъюнктов лишь увеличивает. Так вот дизъюнктов там очень много. Значит из такой КНФ получится задача суммы подмножества с размером элементов множества сильно больше размера модуля. Это задача subset sum с одной стороны.
С другой стороны используем следующий алгоритм. Берём написанную выше задачу дискретного логарифма по простому модулю. Сформируем множество из $a$, взятому по степеням двойки. В полученном множестве путём прибавления модуля к отдельным элементам добьёмся взаимной простоты всех элементов. Найдём остаток от $C$ по каждому элементу множества и применим китайскую теорему об остатках. Если один из элементов множества взяли пропорциональным $2^m$, где $m$- количество бит в модуле $p$, то путём сокращения модуля, получившегося после теоремы об остатках, получаем задачу дискретного логарифма в форме суммы подмножества по модулю
$2^m$. Здесь старый и новый модуль соразмерны, количество лишних решений будет минимально, если вообще будет.
Осталось сравнить размер двух результатов.

[Xaositect]

Tot в сообщении #1109589 писал(а):

С Вашей оценкой размера согласен, но он не имеет значения, так как в задаче сумма подмножества все биты всех элементов этого множества никак не коррелируют друг с другом, являясь по сути случайными величинами с равномерным распределением, так как зависят лишь от наличия каждой переменной в каждом дизъюнкте и наличия у этой переменной знака отрицания. Поэтому применение модуля $2^n$ не должно вызвать появления большого количества лишних решений в среднем по всему массиву булевых функций от $n$ переменных.

Я сильно не уверен. Докажите.

[Tot]

Для доказательства понадобится оракул, решающий $NP$-полные задачи за полиномиальное время, и две монетки. Монеты пронумеруем. Орёл первой монеты - наличие испытуемой переменной в текущем дизъюнкте, решка- отсутствие. Орёл второй монеты - наличие отрицания у испытыуемой переменной в текущем дизъюнкте, решка - отсутствие. Возьмём произвольную КНФ с $n+1$ переменной. Её решение нам неизвестно, но пусть будет только одно. В противном случае попросим оракул убрать переменные множественности решений и переобозначим $n$. Берём первую переменную в первом дизъюнкте, подбрасываем монетки и выставляем запись переменной по монетам. Просим оракул записать в первом дизъюнкте последнюю переменную в форме, при котором дизъюнкт при подстановке решения КНФ по-прежнему давал бы единицу. Проделываем такую процедуру с первой переменной во всех дизъюнктах, затем со второй переменной и так далее до предпоследней переменной также во всех дизъюнктах. Далее просим оракул подставить последнюю переменную. Получили произвольную КНФ с $n$ переменными, запись которых во всех дизъюнктах распределена случайный образом с равномерным распределением. Из этой КНФ получим задачу суммы подмножества с тем же распределением элементов множества. Утверждение доказано.

[Xaositect]

При чем тут КНФ? Вы утверждали, что почти все задачи subset sum не приобретают решений, если их рассматривать по модулю $2^n$, и я просил это доказать. Вы этого не доказали, я даже не понял, в каком смысле Вы употребляете термин "почти все".

[Tot]

Имеем множество КНФ $n+1$ переменной, отвечающих одному и тому же единственному решению. В каждом дизъюнкте все переменые, кроме последней, находятся в случайной позиции с равномерным распределением. Записываем из КНФ задачу булева программирования. Коэффициенты при каждой переменной, кроме последней, в каждом неравенстве стоят в случайной позиции с равномерным распределением. Коэффициент при последней переменной в каждом неравенстве неслучаен, им оракул выравнивал КНФ. После подстановки последней переменной этот коэффициент в каждом неравенстве неслучайным образом повлияет на свободный член. Дальше произведём переход от задачи булева программирования к задаче суммы подмножества. Получим, что все элементы множества являются независимыми, случайными величинами с равномерным распределением, но от них зависит сумма. Потом переходим к остаткам по модулю $2^n$. В следствии того, что все элементы множества случайны можем потребовать такой их набор, который при подстановке всех $2^n$ потенциальных решений дают строго различные $2^n$ вариантов суммы. А сумма у нас получена из исходной КНФ. Поэтому в таком усечённом множестве задача не будет иметь лишних решений. На практике выбор базиса вещь экспоненциальная, поэтому берём случайный набор элементов множества. Тогда набор потенциальных сумм будет не строго различным на всех $2^n$ вариантах. Поэтому у некоторых потенциальных сумм решений не будет, а у некоторых появятся лишние решения, избавиться от которых можно лишь путём увеличения модуля.