Выход из "переборного тупика"?

[0101]

Я, как мне кажется, нашел выход из "переборного тупика".
Предисловие.
Мы хотим решить некоторое булево уравнение Y(x1,…, xi,…,xm) = 1,
где Y(x1,…, xi,…,xm)-булева функция от булевых аргументов.
Чтобы определить, есть ли хоть одно решение у этого уравнения, нужно
перебрать все комбинации значений аргументов x1,…, xi,…,xm.
Я усмотрел в этом переборе аналогию с суммированием некоего ряда.
Т.е. если мы получим сумму значений Y(x1,…, xi,…,xm)
для всех комбинаций x1,…, xi,…,xm и эта сумма будет больше 0,
то уравнение Y(x1,…, xi,…,xm) = 1 имеет решение.
Причем, функция для получения суммы значений Y(x1,…, xi,…,xm)
в каноническом виде (назову ее ФУНКЦИЯ) существует
для любой булевой функции и применяется при рассчете надежности
технических устройств с 60-х годов прошлого века(Логико-вероятностное
исчисление И.А. Рябинина, у меня есть его простое мат. обоснование).
Предполагается, что Y(x1,…, xi,…,xm) представлено формулой
полиномиальной сложности.
Поскольку использование ФУНКЦИИ в каноническом виде не проще
полного перебора, возникает вопрос об упрощении ФУНКЦИЙ для
конкретных классов булевых функций. Для простейших случаев
(бесповторные булевы функции, сумма по модулю 2 всех конъюнций n-й
длины из m булевых переменных, n<=m) упрощенные ФУНКЦИИ получить легко.
С получением более серьезных результатов есть проблемы.
Не вижу особого толка от упрощения выражений как области компьютерной
алгебры в нынешнем ее состоянии, может я неправ, литературные источники скудны.
Вопрос.
Имеют ли научную ценность мои результаты?
Если да, в каком виде это нужно оформить и куда можно пристроить?

[Xaositect]

0101 в сообщении #217239 писал(а):

Предполагается, что Y(x1,…, xi,…,xm) представлено формулой
полиномиальной сложности.

Вот здесь мне видятся основные проблемы.

Насчет бесповторных функций - для бесповторных функций существует полиномиальный алгоритм распознавания выполнимости. Набросок алгоритма:
Алгоритм принимает на вход бесповторную формулу и выдает $\mathbf{F}$, если она тождественно ложна, $\mathbf{T}$ - если тождественно истинна, и $\mathbf{N}$ в остальных случаях.
1. Находим главный символ формулы (линейно отн. длины формулы)
2. Запускаем алг. рекурсивно для двух подформул, связанных главным символом.
3. определяем результат для формулы (например, $\mathbf{T}\vee \mathbf{T} = \mathbf{T}$, $\mathbf{F}\vee \mathbf{N} = \mathbf{N}$, $\mathbf{F}\oplus \mathbf{N} = \mathbf{N}$, $\mathbf{N}\oplus \mathbf{N} = \mathbf{N}$ и т.п.)
Алгоритм использует бесповторность формулы в последнем пункте. Он использует то, что переменные в левой и правой части изменяются независимо.

Трюки, похожие на Ваш(переход от булевых переменным к целым и суммирование) применялись в некоторых задачах, связанных с распознаванием свойств булевых функций, в основном, сохранения некоторых предикатов. Там строились алгоритмы, полиномиальные относительно длины вектора функции($2^n$). В частности, некоторые таким образом построенные алгоритмы рассматриваются в книге В. Б. Алексеева "Введение в теорию сложности алгоритмов".

[0101]

Спасибо! Буду искать книгу Алексеева.

Значит идея уже в голову многим приходила и ценна только в том случае, если удастся упростить до полиномиальной сложности "арифметическую форму" хотя бы для одного класса булевых функций, считающегося NP-полным?

[maxal]

возможно, будет интересна статья:
Н.В.Верещагин, А.Шень Логические формулы и схемы
http://www.mccme.ru/free-books/matpros5.html

[Xaositect]

0101 в сообщении #217427 писал(а):

Значит идея уже в голову многим приходила и ценна только в том случае, если удастся упростить до полиномиальной сложности "арифметическую форму" хотя бы для одного класса булевых функций, считающегося NP-полным?

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

Ну а если удастся упростить, то P=NP. Это, можно сказать, Результат с большой буквы Р.

[0101]

maxal Спасибо! Содержательная статья.

В таком случае непаханным полем является область упрощения выражений. Самой простой представляется задача, предложенная институтом Клэя как пример NP – полной:
м=100 мест в общежитии,п=400 претендентов, список нежелательных пар претендентов (длина списка в общем случае п(п-1)/2=72800)(Список) , ни одной нежелательной пары не должно оказаться в общежитии.
Рассмотрим уменьшенный вариант расселения. м=4 ,п=6 , длина списка нежелательных пар претендентов =15.
Решение задачи может быть получено с помощью булевой функции, канонический вид которой
F=
P12 И P13 И P14 И P23 И P24 И P34 ИЛИ P12 И P13 И P15 И P23 И P25 И P35 ИЛИ P12 И P13 И P16 И P23 И P26 И P36 ИЛИ P12 И P14 И P15 И P24 И P25 И P45 ИЛИ P12 И P14 И P16 И P24 И P26 И P46 ИЛИ P12 И P15 И P16 И P25 И P26 И P56 ИЛИ P13 И P14 И P15 И P34 И P35 И P45 ИЛИ P13 И P14 И P16 И P34 И P36 И P46 ИЛИ P13 И P15 И P16 И P35 И P36 И P56 ИЛИ P14 И P15 И P16 И P45 И P46 И P56 ИЛИ P23 И P24 И P25 И P34 И P35 И P45 ИЛИ P23 И P24 И P26 И P34 И P36 И P46 ИЛИ P23 И P25 И P26 И P35 И P36 И P56 ИЛИ P24 И P25 И P26 И P45 И P46 И P56 ИЛИ P34 И P35 И P36 И P45 И P46 И P56
Где
P12 (элемент списка желательных/ нежелательных пар)-в случае нежелательности пары претендентов №1 - №2 равно 0, в противном случае – 1,
P12 И P13 И P14 И P23 И P24 И P34 – конъюнкция всех значений в Списке для пар претендентов №1, №2, №3, №4.
Если удастся упростить F для уменьшенного варианта задачи, то результат можно попытаться обобщить, в противном случае – довод в пользу безальтернативности перебора.

Мало чем помогает компьютерная алгебра. Вынесение общего множителя за скобки, Карты Карно и т.п. в данном случае неэффективны. Нужен специфический инструмент. Здесь я далеко не продвинулся

[0101]

Нашел я способ упрощать формулу вышеупомянутой задачи для произвольных м и п, раполагая список запрещенных/разрешенных пар в виде треугольника. Правда, упрощенная формула не сильно лучше перебора.
Возвращаюсь к вопросу о "переборном тупике". Он не связан прямо с решением NP-полных задач. Тут суть в другом. Есть к примеру некоторый ряд. Есть формулы для элемента ряда и для его частичной суммы. Правда, формулы не настолько громоздки, чтобы каноническую форму нужно было упрощать.
Если есть компактная форма для некоторой булевой функции, то существует ли компактная форма для ее "суммарной" функции? К какой области математики относится этот вопрос?