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

[Xaositect]

Я по прежнему не понимаю. Запишите строго утверждение, которое обсуждается. В частности, мне неясны следующие вещи: в каком смысле Вы употребляете термин "почти все", говорите ли Вы о всех задачах subset sum, или только о полученных сводимостью из задачи выполнимости? Если только из выполнимости, то опишите конкретно сводимость (или дайте ссылку). Потому что если мы говорим про ту сводимость, которую знаю я, то вот это Ваше утверждение неверно:

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

Далее произведём переход от задачи булева программирования к задаче суммы подмножества. Получим, что все элементы множества являются независимыми, случайными величинами с равномерным распределением [...]

[Tot]

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