Решение 3SAT через упрощение DNF?

Я придумал алгоритм решения проблемы 3SAT с помощью следующего подхода:

1) Возьмите все предложения в уравнении cnf, которые имеют хотя бы одну общую переменную. Найдите все такие комбинации и поместите их в список под названием «Пересечение». Список «Пересечение» теперь содержит группы пересекающихся предложений.

2) Далее мы преобразуем все предложения в определенной группе «Пересечение» в ДНФ. Поскольку будет хотя бы одна общая переменная, я не думаю, что это будет экспоненциальное время.

3) Затем мы преобразуем все полученные ДНФ в одну ДНФ, поскольку все они разделены логическим элементом И в исходном уравнении.

4) Если в полученной ДНФ есть один дизъюнкт, то уравнение выполнимо, иначе уравнение невыполнимо. Это связано с тем, что непересекающиеся предложения (предложения, которые не имеют какой-либо общей переменной) не будут влиять на общее уравнение, и, наконец, если мы «И» с теми с полученным DNF, оно будет только умножать и добавлять переменные к существующим оговорки (если есть).

Мой вопрос:

Каково время выполнения этого алгоритма и доказывает ли это что-либо, связанное с P = NP, поскольку я думаю, что этот алгоритм довольно эффективен. Меня подвели другие в моих предыдущих алгоритмах, поэтому на этот раз, пожалуйста, уделите время анализу алгоритма, поскольку это моя тяжелая работа.


runtime algorithm time-complexity p-np sat
person vinaych    schedule 13.09.2015    source источник
comment
Я нашел ответ на ваш вопрос, который решает проблему P = NP: он слишком мал, чтобы поместиться в этом поле для комментариев.. 42. Увидимся на церемонии вручения наград тысячелетия @Clay..   -  person toddlermenot    schedule 13.09.2015

Ответы (1)


arrow_upward
2
arrow_downward

Я использовал именно этот алгоритм, чтобы сделать решатель тральщика.

На практике это работает очень быстро, когда переменные рассредоточены (как на типичных уровнях тральщика).

Однако для сложной задачи 3-SAT расширение на шагах 2 и 3 до одной ДНФ требует экспоненциального времени, потому что каждый раз, когда мы комбинируем предложения, количество потенциальных терминов увеличивается как произведение длины предложений.

Подводя итог, можно сказать, что это очень полезный подход для некоторых задач SAT, но он имеет экспоненциальную производительность в худшем случае, поэтому ничего не говорит о P=NP.

person Peter de Rivaz    schedule 13.09.2015
comment
LOL, этот ответ сделал мой день ;-) - person toddlermenot; 13.09.2015
comment
Но, может быть, даже на шаге 3 при преобразовании к одной ДНФ мы можем снова взять только те ДНФ (из решенных ДНФ для каждой группы в Пересечении), которые имеют хотя бы одну общую переменную. Я думаю, это не увеличило бы потенциальные сроки в геометрической прогрессии?? - person vinaych; 14.09.2015