Задача о нахождении решения булева уравнения

Tfrn

Есть ли алгоритмы нахождения значений пропозициональных переменных при которых пропозициональная формула принимает значение "истина"?
Понятно, что эта задача будет решена, если привести формулу к ДНФ.
Но этот прием плохо работает при большом количестве переменных.
Задача слишком общая. Может есть методы нахождения решений при каких-то дополнительных условиях (специальный вид формулы,...)

Xephon

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

Tfrn

а что, длина твоей формулы очень большая?
Будем считать порядка 100 переменных, а длина в константу раз больше.
задача проверки истинности NP-полна
Спасибо, не знал.
В общем случае, задача не решается по хорошему.
Но может быть задача решается в частных случаях?
Какие нетривиальные условия можно наложить, чтобы она решалась.
и кроме переборных алгоритмов, кажется, ничего не известно
Мне тоже так кажется.
Но в данном случае, перебор отпадает.

Xephon

есть алгоритм проверки истинности для функции, уже разложенной в ДНФ, если каждый моном имеет длину <=2. для длины 3 задача уже NP-полна. впрочем, я в теории сложности не специалист. советую тебе спросить на мехмате у Шеня или людей с его семинара, может в конкретном случае что-то подскажут.

Tfrn

есть алгоритм проверки истинности для функции, уже разложенной в ДНФ
Вообще-то меня интересует не проверка истинности, а нахождение хотя бы одного решения.
(Допустим существование решения постулировано.)
Так что, если мы получим ДНФ, то по первой скобке находим решение и все.

Xephon

даже если ты найдешь полиномиальный алгоритм для такой упрощенной задачи, то отсюда будет следовать существование полиномиального алгоритма для NP-сложной задачи. достаточно будет запустить твой алгоритм и обрубить его в случае долгой работы (у нас же есть полиномиальная оценка на время а выданный результат проверить на честность, если она что-то выдаст

Tfrn

Я чего то не понимаю в жизни, наверное
Пусть у нас есть ДНФ, или даже СДНФ.
Тогда очень быстро находится одно решение по первому моному.

Xephon

я наврал сильно
там КНФ везде в этих гадостях
с ДНФ, конечно, все просто
извини, пожалуйста
Оставить комментарий
Имя или ник:
Комментарий: