Временные сложности современных саловых решений по отношению к длине формулы

Question

Я узнаю о DPLL и DDCL SAT SAT SAT, и я знаю, что у них есть временная сложность экспоненты для количества переменных.

Если я не ошибаюсь, одна из причин, почему большинство верят P не равно NP, заключается в том, что нет алгоритма многочлена-времени для сента, несмотря на огромные усилия математиков и компьютерных ученых. Тем не менее, проблема P VS NP только заботится о сложности времени относительно длины формулы, а не количества переменных.

Если эти современные SAT-растворители были запущены на формулах 3CNF, то время сложности с временной сложностью к числу переменных подразумевает экспоненту сложности времени до длины 3Cnf.

Однако, если они работали на произвольных CNFS, длина которых может быть экспоненциальной к количеству переменных, то экспоненциальность временной сложности для количества переменных не обязательно подразумевает экспоненту сложности времени до длины CNF.

Таким образом, связанный вопрос, есть ли эти SAT Solvers работают на 3CNF или CNF, в то время как измеряют сложность времени?

Answer 1

для 3sat, количество переменных полиномиально связано с количеством пунктов. (См. Конец для оправдания.)

Следовательно, любой алгоритм для 3SAT, чье время работы - многочлен в количестве пунктов, также будет полиномиальным в количестве переменных; И любой алгоритм для 3SAT, чье время работы - многочлен в количестве переменных, также будет полиномиальным в количестве пунктов.

Известен, что есть алгоритм полиномиального времени для 3SAT, если и только в том случае, если есть алгоритм полиномиального времени для SAT, если и только в том случае, если есть алгоритм полинома-времени для Circuitsat (например, для формул) Отказ Кроме того, несмотря на десятилетия работы на SAT Solvers, никто не знает ни одного алгоритма для 3SAT, который проходит в многочленом времени (или действительно менее чем в экспоненте в худшем случае). Вы можете принять это как доказательства того, что для 3SAT нет алгоритма многонового времени; Что подразумевает, что нет алгоритма многонового времени для SAT или Circuitsat, а также подразумевает, что P!= NP.

---

Обоснование: Пусть $ n $ обозначает количество переменных и $ m $ Количество пунктов Отказ У нас есть $ n \ Le 3M $ (переменная, которая не отображается в любом пункте, не может быть проигнорирована) и $ m \ le 8n ^ 3 $ (в каждом пункте есть три литерала, и вы можете игнорировать повторные пункты). Отсюда следует, что $ n / 3 \ le m \ le 8n ^ 3 $ и $ \ sqrt [3] {м / 8} \ le n \ le 3m $ , т. Е. Каждый полиномиально связан с другим.

---

Я вижу, что вы пересмотрели свой вопрос. Что разъясняет, что я думаю, что у вас есть неправильное представление. Вы говорите о «Run [Ning] [SAT Solver] на произвольных логических формулах». Однако вы не можете запустить SAT Solver на произвольной логической формуле. SAT Solvers работают только на формулах CNF.

Однако мы знаем, что любая логическая формула может быть преобразована в эквредиразвичную формулу CNF размером с большинства полиномиальных в размере формулы и наоборот. Если бы у вас был алгоритм, который мог бы проверить удовлетворение произвольных булевых формул во времени многочлен в размерах формулы, то после этого следует, что у вас есть алгоритм, который мог бы проверить выполнение формул 3CNF во времени многочлена в размере формулы (каждый Формула 3CNF - это логическая формула), и, следовательно, алгоритм, который мог бы проверить удовлетворение формул 3CNF во времени многочлена в количестве переменных - что противоречит именному доказательствам. Итак, если вы считаете, что нет алгоритма для решения 3SAT во времени многочлена в количестве переменных, то вы также должны полагать, что нет алгоритма для проверки активной активности произвольных логических формул во времени многочлена в размере формулы. < / P >.