В другой ветке Джо Фитцсимонс спросил о «лучших текущих нижних границах на 3SAT».
Я хотел бы пойти по другому пути: каковы лучшие текущие верхние границы на 3SAT? Другими словами, какова временная сложность наиболее эффективного SAT-решателя?
В частности, возможно ли найти субэкспоненциальный (но суперполиномиальный) алгоритм для SAT?
cc.complexity-theory
ds.algorithms
sat
upper-bounds
М.С. Дусти
источник
источник
Ответы:
Есть два вида «лучших» SAT решателей, один для теории, один для практики.
теория
практика
Проверьте конференцию SAT на результаты соревнований за каждый год.
источник
Я не знаю ни нулевых ошибок рандомизированных алгоритмов (или Cone / Eadvice алгоритмов,
по этому вопросу) для SAT , которые имеют лучшие оценки , чем известных детерминированных алгоритмов,
независимо от того , есть или нет обещало быть максимально удовлетворяющая присваивание.
требует результата, который можно суммировать следующим образом:
источник
Алгоритм Шенинга является вероятностным алгоритмом для k-SAT со временем выполнения , где . Это приводит к алгоритму для 3SAT, алгоритму для 4SAT и т. Д.O(an) a=2(k−1)/k O(1.33334n) O(1.5n)
Алгоритм также (почти полностью) дерандомизирован Мозером и Шедером, которые дают детерминистический алгоритм для решения времени работы kSAT где такая же константа, как и раньше, и может быть сделано сколь угодно маленьким.O((a+ϵ)n) a ϵ>0
Примечание. В этом ответе в большой записи Oh скрываются поли (n) факторы. Я хотел использовать нотацию , но она не отображается должным образом.O∗
источник
Как уже упоминалось, если вас интересуют теоретические гарантии времени выполнения, этот вопрос является дубликатом.
Но я хотел бы отметить, что если вы действительно хотите решить конкретную проблему (например, проблему окраски, о которой вы упоминали), я думаю, что совершенно бессмысленно изучать теоретические верхние границы.
Несмотря на то, что вы хотели избежать «инженерных» аспектов, я бы посоветовал вам просто взять некоторые популярные решатели SAT, опробовать их и посмотреть, что произойдет (большинство из них могут читать один и тот же формат файла DIMACS, поэтому его легко попробовать разные решатели). У вас могут быть как положительные, так и отрицательные сюрпризы. Недавно у меня была семья SAT; оказалось, что множество примеров с десятками тысяч переменных и более чем миллионом предложений оказалось легко решить, в то время как, казалось бы, гораздо более простые примеры с сотнями переменных и тысячами предложений были слишком сложными для любого решателя, который я пробовал.
источник
источник
Для 3SAT невозможно иметь субэкспоненциальные алгоритмы, если гипотеза экспоненциального времени не ложна.
источник
Этот пост посвящен верхним границам SAT. Это одно дело с лучшими нижними границами. По этой ссылке дается подробная информация о ежегодном конкурсе, в котором сравниваются реализации SAT solver, которые можно загрузить. Для простоты вы можете начать с SAT4J , библиотеки на основе Java для решения SAT.
источник
Лучший детерминированный алгоритм для 3-SAT теперь имеет верхнюю границу 1.32793 ^ n, см. Https://arxiv.org/abs/1804.07901 от Sixue Liu. В основном, верхние границы для всех k-SAT были улучшены в этой статье.
источник