Лучшие верхние границы на SAT

43

В другой ветке Джо Фитцсимонс спросил о «лучших текущих нижних границах на 3SAT».

Я хотел бы пойти по другому пути: каковы лучшие текущие верхние границы на 3SAT? Другими словами, какова временная сложность наиболее эффективного SAT-решателя?

В частности, возможно ли найти субэкспоненциальный (но суперполиномиальный) алгоритм для SAT?

М.С. Дусти
источник
2
Я не знаю об аналитических результатах, но вы можете найти экспериментальные результаты здесь baldur.iti.uka.de/sat-race-2010/results.html (см. Ссылки "HTML")
Radu GRIGore
1
название этого вопроса немного вводит в заблуждение из-за существования этого вопроса: cstheory.stackexchange.com/questions/1295/sat-solver-download . Я думаю, что вы могли бы перефразировать как «Лучшие верхние границы на SAT»?
Суреш Венкат
@Suresh: вопрос, на который вы ссылаетесь, относится к "#SAT", а этот соответствует SAT. Кроме того, этот вопрос был задан примерно через неделю после этого. В любом случае, вы все еще предлагаете изменить название этих?
MS Dousti
да, потому что "SAT Solver" - это конкретный хорошо известный объект - фактическая кодовая база для решения SAT. Google запутается и перенаправит людей, которые ищут код здесь :).
Суреш Венкат
4
Что касается мотивации этого вопроса, я подумал, что несколько человек попробовали SAT-решатели в 17x17 случаях. Кажется, это граница того, что может быть решено с помощью SAT-решателя. Вместо этого вы могли бы попробовать параллельный решатель, но у меня сложилось впечатление, основываясь на сообщениях Билла Гасарха, что вам потребуются масштабные усилия. Вы также можете применить решатель SMT с подходящей теорией или использовать решатель ограничений, который реализует глобальное ограничение с эффективным пропагатором. В каждом из этих случаев новой идеей будет выражение важного свойства, которое трудно сделать с помощью предложений.
Андрас Саламон

Ответы:

38

Есть два вида «лучших» SAT решателей, один для теории, один для практики.

теория

рандомизированный для 3SAT.O(1.32113n)

рандомизированный для 3SAT.O(1.321n)

детерминированный для 3SAT.O(1.439n)

практика

Проверьте конференцию SAT на результаты соревнований за каждый год.

Тян Лю
источник
Я нашел ссылку на Ивама и соавт. бумага . Итак, действительно ли самый последний и лучший результат для решения SAT до сих пор? O(1.32113n)
MS Dousti
@ Садек: Я так думаю, но только для 3-SAT, а не SAT.
Тян Лю
2
Теперь лучший алгоритм за времени - Тимон Хертли, Робин А. Мозер и Доминик Шедер. O(1.321n)
Тянь Лю
10
Еще одно обновление: в FOCS 2011 Тимон Хертли ( arxiv.org/abs/1103.2165 ) доказал, что алгоритм PPSZ решает каждый экземпляр 3SAT за раза. 1.308n
Райан Уильямс
21

Я не знаю ни нулевых ошибок рандомизированных алгоритмов (или Cone / Eadvice алгоритмов,
по этому вопросу) для SAT , которые имеют лучшие оценки , чем известных детерминированных алгоритмов,
независимо от того , есть или нет обещало быть максимально удовлетворяющая присваивание.


«Проблема 3-SAT детерминированно разрешима во времени ».O(1.3303n)


«Для однозначно удовлетворяемого 3-CNF (соответственно 4-CNF) по переменным удовлетворяющее назначение может быть найдено в детерминированном времени выполнения не более (соответственно ). "оn
ОO(1.3071n)O(1.4699n)


  1. «Существует рандомизированный алгоритм для 3-SAT с
    односторонней ошибкой, который выполняется во времени ». O(1.30704n)
  2. «Существует рандомизированный алгоритм для 4-SAT с
    односторонней ошибкой, который выполняется во времени ».O(1.46899n)


«Существует рандомизированный алгоритм для уникального 3-SAT, такой что для и - действительное число, позволяющее ограничить время выполнения предыдущей статьи для 3-SAT в виде , Настоящий документ в алгоритм работает во времени . "ϵ=1/(1024)
S
O(2(S+o(1))n)O(2(Sϵ+o(1))n)


Сообщество
источник
16

Алгоритм Шенинга является вероятностным алгоритмом для k-SAT со временем выполнения , где . Это приводит к алгоритму для 3SAT, алгоритму для 4SAT и т. Д.O(an)a=2(k1)/kO(1.33334n)O(1.5n)

Алгоритм также (почти полностью) дерандомизирован Мозером и Шедером, которые дают детерминистический алгоритм для решения времени работы kSAT где такая же константа, как и раньше, и может быть сделано сколь угодно маленьким.O((a+ϵ)n)aϵ>0

Примечание. В этом ответе в большой записи Oh скрываются поли (n) факторы. Я хотел использовать нотацию , но она не отображается должным образом.O

Робин Котари
источник
1
Почему вы говорите «почти полностью»? Я что-то пропустил в газете?
Андрас Саламон
1
Существует восемь детерминистических алгоритмов для k-SAT, поэтому, пожалуйста, прости меня, не упоминая их всех. Вот ссылка: linkinghub.elsevier.com/retrieve/pii/S0304397501001748 . Таким образом, для у нас есть и это не так хорошо, как другие оценки для 3-SAT, представленные здесь, но для k-SAT это лучший, насколько я знаю. k=3O(1,5n)O((22k+1)n)k=3O(1.5n)
Григорий Ярославцев
4
Я сказал «почти полностью», просто чтобы указать, что там есть эпсилон-фактор. Я предполагаю, что можно ожидать, что полная дерандомизация достигает того же времени выполнения (вплоть до полиномиальных факторов). Или, может быть, это неразумно ожидать.
Робин Котари
1
@ Григорий Ярославцев: Не является ли детерминированный алгоритм Мозера-Шедера для kSAT, который я упомянул, быстрее, чем тот, который вы цитировали? Я что-то пропустил?
Робин Котари
1
Я просто беспокоился об этом в вашей записи, так что это действительно быстрее. Похоже, что статья появилась на arXiv всего несколько дней назад: arxiv.org/PS_cache/arxiv/pdf/1008/1008.4067v1.pdf , поэтому неудивительно, что я не знал об этом. ϵ
Григорий Ярославцев
12

Как уже упоминалось, если вас интересуют теоретические гарантии времени выполнения, этот вопрос является дубликатом.

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

Несмотря на то, что вы хотели избежать «инженерных» аспектов, я бы посоветовал вам просто взять некоторые популярные решатели SAT, опробовать их и посмотреть, что произойдет (большинство из них могут читать один и тот же формат файла DIMACS, поэтому его легко попробовать разные решатели). У вас могут быть как положительные, так и отрицательные сюрпризы. Недавно у меня была семья SAT; оказалось, что множество примеров с десятками тысяч переменных и более чем миллионом предложений оказалось легко решить, в то время как, казалось бы, гораздо более простые примеры с сотнями переменных и тысячами предложений были слишком сложными для любого решателя, который я пробовал.

Юкка Суомела
источник
8
В дополнение к резюме Юкки, также стоит отметить, что есть два основных типа решателей SAT: те, которые основаны на распространении результатов опроса, которые хорошо работают для случайных экземпляров SAT, и те, которые используют обучение по пунктам в сочетании с разрешением по единицам, что имеет тенденцию работать хорошо открыть комбинаторную структуру. У них совсем другое поведение. Наихудшими случаями для решателей SAT являются, как правило, случаи, которые не могут быть удовлетворены, но где пространство nogoods имеет сложную структуру, которая не допускает большого сокращения. К сожалению, примеры из комбинаторики, как правило, такого рода.
Андрас Саламон
11

детерминированный для 3SAT.O(1.308n)

каве
источник
Я предполагаю, что когда кто-то придумывает лучшую верхнюю границу, он цитирует эту статью. Только однажды цитировалась эта статья: «Алгоритм удовлетворенности и средняя жесткость для формул по полному двоичному базису», и они, похоже, говорят только об определенных типах формул. Таким образом, это, похоже, лучший верхний предел на данный момент.
Тайфун платят
@TayfunPay: нижняя статья в моем ответе цитирует эту статью.
@RickyDemer Ух! это лучше, чем это связано? Запись не так понятна для меня.
Tayfun Pay
@TayfunPay: Да, и вы можете охотиться через две бумаги, как описано ниже. На странице 5 общей статьи 3-SAT они дают значение , сообщают время выполнения алгоритма PPSZ для уникального k-SAT в терминах и говорят, что они имеют одинаковую границу для общего k-SAT. В верхней части страницы 11 эта статья говорит, что их алгоритм дает ту же границу, что и PPSZ, что означает, что они не показали ничего большего, чем я упомянул в моем предыдущем предложении. (продолжение ...)S kS3Sk
(... продолжение) На странице 2 уникальной статьи 3-SAT они дают значение и говорят, что их алгоритм дает оценку, которая лучше, чем , на явную экспоненциальную величину , Так как из моего предыдущего предложения равно из предложения до этого, граница уникальной статьи 3-SAT экспоненциально лучше, чем общая граница статьи 3-SAT. 2 S nS2SnS 3SS3
8

Для 3SAT невозможно иметь субэкспоненциальные алгоритмы, если гипотеза экспоненциального времени не ложна.

рандомизированный алгоритм с ожидаемым временем выполнения для 3SAT.O(1.324n)

рандомизированный алгоритм с ожидаемым временем выполнения для 3SAT.O(1.32216n)

Мухаммед Аль-Туркистани
источник
15
Разве это не тавтология?
Цуёси Ито
1
Да, это тавтология: гипотеза экспоненциального времени (ETH) состоит в том, что 3SAT, проблема выполнимости булевых формул в конъюнктивной нормальной форме с не более чем тремя литералами в предложении и с n переменными, не может быть решена за время . (См .: Википедия ). 2o(n)
MS Dousti
Работа Kazuo Iwama et al. (2004) новее, чем у Шоенинга (1999). Интересно, есть ли еще более свежие результаты?
MS Dousti
8
Во избежание путаницы мой последний комментарий относится к первому предложению ответа: «Для 3SAT невозможно иметь субэкспоненциальные алгоритмы, если гипотеза об экспоненциальном времени (ETH) не ложна». Я понимаю, что экспоненциальное время Гипотеза является самой гипотезой, утверждающей, что не существует алгоритма для 3SAT, время работы которого является субэкспоненциальным (т.е. 2 ^ {o (n)}) по числу переменных.
Цуёси Ито
10
И чтобы избежать дальнейшей путаницы, я добавлю, что когда Цуёси опубликовал свой комментарий, ответ содержал только одно предложение, что сделало его комментарий очень уместным.
Робин Котари
7

Этот пост посвящен верхним границам SAT. Это одно дело с лучшими нижними границами. По этой ссылке дается подробная информация о ежегодном конкурсе, в котором сравниваются реализации SAT solver, которые можно загрузить. Для простоты вы можете начать с SAT4J , библиотеки на основе Java для решения SAT.

Дэйв Кларк
источник
Оказывается, этот вопрос был уже задан до; Я просто не видел его, когда искал на сайте. Ответ Тянь Лю на вопрос о верхних границах - это именно то, что я искал. Спасибо за ссылки, Дэйв!
Даниэль Апон
1
Это доказательство того, что я провожу здесь слишком много времени ;-)
Дэйв Кларк,
мы рады, что вы делаете :)
Суреш Венкат
2
Я не уверен, что рекомендую sat4J, он не только значительно медленнее, чем современный, но и несколько более сложный. Это правда, однако, что он хорошо настраивается благодаря объектно-ориентированной структуре. MiniSat очень хорошо написан, и 2.2 является современным.
Миколас
3

Лучший детерминированный алгоритм для 3-SAT теперь имеет верхнюю границу 1.32793 ^ n, см. Https://arxiv.org/abs/1804.07901 от Sixue Liu. В основном, верхние границы для всех k-SAT были улучшены в этой статье.

ON KI Wong
источник