Теоретические объяснения практического успеха SAT решателей?

43

Какие теоретические объяснения есть для практического успеха решателей SAT, и может ли кто-нибудь дать обзор и объяснение в стиле «википедии», связав их всех вместе?

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

Я немного слышал о таких вещах, как бэкдоры, структура графа предложений и фазовые переходы, но (1) я не вижу, как все они сочетаются друг с другом, чтобы дать более широкую картину (если они есть), и (2) Я не знаю, действительно ли они объясняют, почему решатели SAT работают так хорошо, например, в промышленных случаях. Кроме того, когда дело доходит до таких вещей, как структура графа предложений: почему текущие решатели могут использовать преимущества определенных структур графа предложений?

Я только нахожу результаты о фазовых переходах, частично удовлетворяющие в этом отношении, по крайней мере, в моем в настоящее время ограниченном понимании. Литература о фазовых переходах посвящена случаям случайного k-SAT, но действительно ли это что-то объясняет в реальных случаях? Я не ожидаю, что реальные экземпляры SAT будут выглядеть как случайные; нужно ли мне? Есть ли причина думать, что фазовые переходы говорят нам что-то, даже интуитивно, об экземплярах реального мира, даже если они не похожи на случайные экземпляры?

Связанные вопросы, которые помогают, но не полностью отвечают на мой вопрос, особенно просьба связать вещи в единую картину:

Джошуа Грохов
источник
5
Это не ответ, но я не думаю, что многие люди все еще верят, что графовые структуры / бэкдоры могут объяснить работу решателей SAT. Они кажутся более актуальными для более сложных задач, таких как #SAT, QBF или компиляция знаний, где вам действительно нужно найти умные факторизации, так как вам нужно как-то исследовать всю структуру. На ваш вопрос я испытываю желание ответить: «На самом деле никто не знает, и это активная область исследований». Но мне нужно собрать ссылки, чтобы показать, что люди пытаются, и может быть кто-то с более широким взглядом, чем я, который может дать лучший ответ.
holf
2
@ Джошуа: Симплексный метод даже PSPACE-могучий (Фернли и Савани, STOC 15).
Рахул Савани
1
Я согласен с @holf. Вот мои несколько центов: SAT решатели могут восстанавливаются быстрее , чем НСП решатели , потому что все их переменные имеют размер домена два. Это не означает, что ни один CSP-решатель не может превзойти SAT-решатель, он может, если он обладает очень сложной динамической переменной (а также значением), упорядочивая эвристику в сочетании с хорошим кодированием проблемы. Кроме того, когда вы превращаете «реальный экземпляр» в экземпляр SAT, вы редко попадаете в точку фазового перехода из-за введения такого количества вспомогательных переменных. UsUaLLY
Тайфун
3
@TayfunPay: я не ставил под сомнение ваш опыт - на самом деле, я на 100% уверен, что «реальные» проблемы перерастают в случаи SAT, которые не близки к фазовому переходу. Но я не думаю, что это объясняет легкость таких случаев, так как эти случаи не случайны , поэтому фазовый переход (в теории) должен иметь мало что сказать о них (твердость или легкость).
Джошуа
2
Это уже упоминалось в другом месте, но важно отметить, что плотность с переменным условием и фазовые переходы имеют значение только для случайных k-SAT и не имеют ничего общего с твердостью примеров, возникающих из промышленных или комбинаторных проблем. Таким образом, большая часть обсуждения выше не относится к делу. Кроме того, стоит отметить, что в отношении случайного k-SAT не существует реальной схемы «легко-трудно-легко-легко» - для систем доказательства, где мы имеем нижние оценки для случайно сгенерированных формул k-CNF, формулы остаются экспоненциально сложными для произвольно большой константы плотности выше порога.
Якоб Нордстрем

Ответы:

21

Я предполагаю, что вы имеете в виду решатели CDCL SAT в наборах эталонных данных, подобных тем, которые использовались в SAT Competition . Эти программы основаны на многих эвристиках и множестве оптимизаций. На семинаре « Теоретические основы прикладного SAT-решения в Банфе» в 2014 году было несколько очень хороших введений в их работу ( видео ).

Эти алгоритмы основаны на алгоритме обратного отслеживания DPLL, который пытается найти удовлетворительное назначение, устанавливая значения для переменных и обратных путей, когда обнаруживает конфликт. Люди смотрели на то, как сильно влияет эта эвристика. Например увидеть

Кажется, что эффективность этих решателей SAT в тестах основывается в основном на двух двух эвристиках (и их вариантах):

  1. VSIDS эвристическая ель, выбирающая, какая переменная будет переходить на следующую.
  2. CDCL: конфликтно-ориентированное предложение, изучающее эвристику, которая изучает новое предложение из конфликта.

Хорошо известно, что доказательства DPLL соответствуют доказательствам в резолюции. Без CDCL единственные доказательства разрешения, которые мы можем получить, являются доказательствами разрешения дерева, которые намного слабее, чем доказательства общего разрешения.

Есть результаты, которые показывают, что с CDCL мы можем получить любое общее доказательство разрешения. Однако есть предостережения, они нуждаются во многих искусственных перезапусках, искусственном ветвлении и / или особой предварительной обработке, поэтому неясно, насколько они близки к тому, что эти программы делают на практике. См., Например, следующую статью для более подробной информации:


CDCL по сути вырезает ветви из пространства поиска. Существуют различные способы вывести новое усвоенное положение из конфликта. В идеале мы должны добавить набор минимальных предложений, которые подразумевают конфликт, но на практике это может быть большим и дорогостоящим для вычисления. Лучшие специалисты по SAT часто удаляют выученные предложения регулярно, и это помогает на практике.


αF(v,я)я0<α<1vN

Σя<NF(v,я)α(N-я)

Интуитивно можно сказать, что это пытается подчеркнуть переменные, которые были последовательно вовлечены в недавние конфликты, Вы также можете думать об этом как об упрощенном, но чрезвычайно дешевом способе прогнозирования того, какие переменные будут вовлечены в следующий конфликт. Таким образом, VSIDS сначала разветвляет эти переменные. Можно утверждать, что алгоритм по сути является отказоустойчивым алгоритмом, быстро находите конфликты. Быстрый относится к меньшему количеству установленных переменных, что означает блокировку больших поддеревьев дерева поиска. Но это в основном интуиция, на самом деле, никто не очень тщательно ее формализовал, чтобы протестировать ее на наборах данных SAT. Запуск решателя SAT для одного из этих наборов данных недешев, не говоря уже о сравнении его с оптимальными решениями (наименьшее расширение текущего присваивания переменным, которое будет нарушать одно из условий). VSIDS также зависит от того, какие переменные мы выделяем при каждом конфликте. Существуют различные способы определения того, когда переменная участвует в конфликте.


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

Существуют также предположения о том, что за исключением конкурирующих экземпляров, подобных тем, которые основаны на NP-сложных задачах, криптографических примитивах и случайных экземплярах (которые не очень хорошо решают CDCL SAT), остальные экземпляры происходят из очень хорошо структурированных вещей, таких как проверка программного и аппаратного обеспечения и так или иначе Структуры эксплуатируются решателями CDCL SAT (было упомянуто много идей, таких как бэкдоры, замороженные переменные и т. д.), но на самом деле они в основном являются идеями и не дают убедительных теоретических или экспериментальных данных, подтверждающих их. Я думаю, что нужно было бы строго определить надлежащим образом и показать, что экземпляры, на которых хорошо работают эти алгоритмы, обладают свойством, а затем показать, что эти алгоритмы используют эти свойства.


Некоторые люди продолжают настаивать на том, что соотношение пунктов и порогов - единственная игра в городе. Это определенно неверно, поскольку любой, кто немного знаком с тем, как работают промышленные SAT-решатели, или знает о сложности доказательства. Есть много вещей, которые делают решатель SAT хорошо работающим или не работающим на экземпляре на практике, и соотношение предложений - только одна из вещей, которые могут быть вовлечены. Я думаю, что следующий обзор является хорошей отправной точкой для изучения связей между сложностью доказательства и решателями и перспективой SAT:

Интересно, что даже пороговое явление является более сложным, чем думает большинство людей, Моше Варди заявил в своем выступлении « Фазовые переходы и сложность вычислений », что среднее время работы GRASP остается экспоненциальным для случайных формул 3SAT после порога, но показатель уменьшается (afaik, непонятно как быстро оно уменьшается).


Почему мы изучаем SAT решатели (как теоретики сложности)? Я думаю, что ответ такой же, как и для других алгоритмов: 1. сравнить их, 2. найти их ограничения, 3. разработать лучшие, 4. ответить на фундаментальные вопросы теории сложности.

При моделировании эвристики мы часто заменяем эвристику недетерминизмом. Тогда возникает вопрос, является ли это «справедливой» заменой? И здесь под честностью я подразумеваю, насколько близка модель, помогающая нам ответить на вопрос выше.

Когда мы моделируем SAT-решатель как систему доказательств, мы частично показываем его ограничение, потому что алгоритм будет неэффективен для утверждений, которые имеют более низкие оценки в системе доказательств. Но все еще существует разрыв между тем, что алгоритм фактически находит, и оптимальным доказательством в системе доказательств. Таким образом, мы должны показать, что и обратное, то есть алгоритм может найти доказательства, которые так же хороши, как и в системе доказательств. Мы не близки к тому, чтобы ответить на этот вопрос, но количество эвристики, которая заменяется недетерминизмом, определяет, насколько модель близка к системе доказательств. Я не ожидаю, что мы полностью отбросим замену эвристики недетерминизмом, иначе мы бы получили результаты автоматизируемости, которые повлияют на открытые проблемы в криптографии и т. Д.

Таким образом, при рассмотрении модели возникает вопрос: насколько модели помогают объяснить, почему решатель SAT A лучше, чем решатель SAT B? Насколько они полезны в разработке лучших SAT решателей? Находит ли SAT-решатель на практике доказательства, близкие к оптимальным в модели? ... Нам также нужно смоделировать практические примеры.

Что касается интуиции, что решатели CDCL SAT «эксплуатируют структуру практических примеров» (независимо от того, что это за структура), я считаю общепринятой интуицией. Реальный вопрос заключается в том, чтобы убедительно объяснить, что это значит, и продемонстрировать, что это действительно так.

См. Также собственный ответ Якоба Нордстрема о последних событиях.

Кава
источник
1
Это относится к экземплярам SAT, полученным из целочисленного факторинга?
Мухаммед Аль-Туркистани
1
часеUряsTясчасеUряsTясs
Tayfun Pay
1
@Martin, без CDCL мы получаем только очень ограниченные формы разрешения (я не помню точно, что у меня в голове). Результаты Пола Бима и других, которые показывают, что с CDCL и перезапусками вы можете получить любое общее доказательство разрешения (однако выбор точек перезапуска и ответвлений является искусственным), подробности см. В статье Бима.
Каве
3
@Martin, см. Также опрос Якоба Нордстрома: csc.kth.se/~jakobn/project-proofcplx/docs/…
Каве
1
Что касается сложности доказательства и CDCL, то Pipatsrisawat и Darwiche показали sciencedirect.com/science/article/pii/S0004370210001669 и независимо друг от друга Atserias, Fichte и Thurley jair.org/papers/paper3152.html, что CDCL, рассматриваемый как система доказательства, может полиномиально смоделировать разрешение (в статьях приводятся разные результаты, но доказательства в обеих статьях могут быть использованы для получения результатов в другой статье). Важным отличием от предыдущих работ в этой области исследований является то, что в этих моделях CDCL нет ничего особенного. [Продолжение следует ...]
Якоб Нордстрем
17

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

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

Если бы нужно было дать ответ в одно предложение, то я думаю,

никто на самом деле не знает, и это активная область исследований

почти так же хорошо, как и получается. За исключением того, что есть гораздо больше возможностей для большей активности, особенно с точки зрения теории.

Некоторые предложенные объяснения (не взаимоисключающие), которые уже обсуждались в других ответах и ​​комментариях,

  • (а) черный ход,
  • (б) параметризованные соображения сложности,
  • (в) графовая структура задачи КНФ,
  • (d) соображения сложности доказательства и
  • (е) фазовые переходы.

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

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

Параметризованная сложность (b) дает прекрасную теорию о некоторых аспектах SAT, и очень привлекательная гипотеза состоит в том, что экземпляры SAT просты, потому что они, как правило, «близки к некоторому островку управляемости». Я думаю, что эта гипотеза открывает много интересных направлений исследований. Как отмечено в некоторых ответах, существует много связей между (а) и (б). Однако до сих пор я не вижу никаких доказательств того, что параметризованная сложность слишком сильно коррелирует с тем, что происходит на практике. В частности, кажется, что примеры, которые можно отследить, могут быть очень, очень трудными на практике, и случаи без каких-либо маленьких бэкдоров все еще могут быть очень легкими.

Объяснение, которое кажется мне наиболее правдоподобным для промышленных случаев, заключается в (с), а именно в том, что (график) структура рассматриваемых формул CNF должна коррелировать с практической эффективностью SAT. Идея здесь в том, что переменные и предложения промышленных экземпляров могут быть сгруппированы в хорошо связанные сообщества с небольшим количеством связей между ними, и что решатели SAT так или иначе используют эту структуру. К сожалению, кажется довольно трудно определить это более жестко, и в равной степени, к сожалению, эта область страдает от обмана. Предложенные объяснения, которые я видел до сих пор в статьях, совершенно неудовлетворительны, и модели, кажется, легко сбить. Казалось бы, проблема в том, что если кто-то действительно хочет сделать это тщательно, тогда математика становится действительно трудной (потому что это сложная проблема), и она также становится чрезвычайно запутанной (потому что ваша модель должна быть достаточно близкой к реальности, чтобы получить релевантные результаты). В частности, в работах, которые я видел, объясняется, что производительность эвристики VSIDS (переменной затухающей суммы, не зависящей от состояния переменной) для выбора переменных работает хорошо, потому что исследует сообщества в графическом представлении примеров, довольно неубедительно, хотя гипотеза как таковая все еще остается неубедительной. очень привлекательный.

Одно направление исследований, которое я лично проводил, заключается в том, насколько практическая эффективность SAT как-то соотносится с показателями сложности доказательств рассматриваемых формул CNF. К сожалению, короткий ответ, похоже, заключается в том, что на самом деле нет четкой и убедительной связи. Возможно, все еще существуют нетривиальные корреляции (это то, что мы в настоящее время исследуем по-разному), но теория кажется слишком красивой, чистой и красивой, а реальность слишком запутанная, чтобы быть действительно подходящим. (Относительно статьи, относящейся к мерам доказательства сложности и практической твердости SATJärvisalo, Matsliah, Nordström и Živný из CP '12 выяснили, что более подробные эксперименты дают гораздо более сложную картину с менее четкими выводами - мы надеемся получить полную версию журнала, сообщающую об этом в любое десятилетие, но это сложно, хотя все еще надеюсь, интересно.)

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

Тем не менее, двумя статьями, которые действительно следует упомянуть в качестве исключений к этому, являются [Pipatsrisawat and Darwiche 2011] и [Atserias, Fichte and Thurley 2011], где показано, что основанные на конфликте решения для обучения SAT, моделируемые естественным образом, имеют потенциал для полиномиального моделирования полного, общего разрешения. Существует довольно длинный список работ, предшествующих [PD11] и [AFT11], которые, по сути, претендуют на один и тот же результат, но все они имеют серьезные проблемы с моделированием. (Это правда, что [PD11] и [AFT11] также нужны некоторые допущения для работы, но они в значительной степени минимальны, которые вы ожидаете, если только вы не запрашиваете документы, которые также показывают, что иерархия параметризованной сложности разрушается.)

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

Доклад в стиле учебника «Взаимодействие между сложностью доказательства и решением SAT», проведенный в Международной летней школе по теории удовлетворенности, теории удовлетворенности и автоматизированного мышления в 2016 году, с множеством полных ссылок в конце слайдов: http://www.csc .kth.se / ~ jakobn / исследования / TalkInterplaySummerSchool2016.pdf

Немного более свежие и краткие доклады об опросах Понимание решения SAT на основе конфликтов с помощью объектива доказательства сложности с начала 2017 года (также с полными ссылками в конце): http://www.csc.kth.se/~jakobn/research /TalkProofComplexityLensCDCL1702.pdf

Обзор связей между сложностью доказательства и решением SAT: http://www.csc.kth.se/~jakobn/research/InterplayProofCplxSAT.pdf [Библиографическая ссылка: Якоб Нордстрем. О взаимодействии между проверкой сложности и SAT-решением. ACM SIGLOG Новости, том 2, номер 3, страницы 19-44, июль 2015 года. (Слегка отредактированная версия с некоторыми исправлениями опечаток.)]

Документ SAT '16 с CDCL, честно смоделированный как система доказательств: http://www.csc.kth.se/~jakobn/research/Trade-offsTimeMemoryModelCDCL_SAT.pdf [Библиографическая ссылка: Ян Элферс, Ян Йоханнсен, Массимо Лаурия, Томас Магнард Якоб Нордстрем и Марк Виньялс. Компромиссы между временем и памятью в более узкой модели CDCL SAT Solvers. В материалах 19-й Международной конференции по теории и применениям тестирования удовлетворенности (SAT '16), Конспект лекций в области компьютерных наук, том 9710, страницы 160-176, июль 2016 года.]

Якоб Нордстрем
источник
16

Позвольте мне добавить к этому два моих цента понимания, хотя я никогда не работал в этой области.

Вы задаете один из двух вопросов: «Каковы все известные подходы к доказательству теоретической эффективности некоторого решателя SAT для некоторого типа экземпляров» и «почему решатели SAT эффективны в реальности».

По первому вопросу я просто направлю вас к исследованию Стефана Шейдера. Мне кажется, что он в настоящее время является наиболее активной областью в области бэкдоров и параметризации FPT в SAT (которая включает в себя как структурные подходы, такие как меры типа treewidth и так называемые наборы бэкдоров, так и некоторую смесь двух).

Что касается последнего вопроса, то, честно говоря, именно этот вопрос обсуждался на каждом семинаре по SAT-решению, который я посещал (включая последние годы), так что это не решенный вопрос. Но у меня сложилось такое впечатление.

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

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

Итак, мы задаемся вопросом, почему решатели на основе CDCL так хорошо работают в промышленных случаях, например, проверки цепей (проверка эквивалентности цепей)? Я думаючто наиболее мощное представление (или консенсусное представление) здесь - это стратегия поиска CDCL, решающей гели очень хорошо со структурой этих примеров. Это означает, например, что схемы состоят из относительно сложных частей (называемых ими кластерами), связанных между собой относительно меньшим количеством и более простыми соединениями, возможно, иерархическим образом; и что решатели CDCL со всей их эвристикой очень хорошо (де-факто) используют это и "проецируют" эти кластеры на общие переменные любым способом или в порядке, наиболее полезном для проверки имеющейся схемы. Но, по-видимому, все еще остается единодушное мнение о том, что это недостаточное объяснение (например, мы, вероятно, не можем теоретически объяснить эффективность решателей CDCL SAT в этой области, просто ссылаясь на структуру графа экземпляра).

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

Магнус Вальстрём
источник
2
Магнус, у тебя определенно больше опыта в этой области, чем у кого-либо еще, кто пытался ответить на этот вопрос до сих пор. Когда я указывал «мои два цента», я имел в виду тот факт, что я изучил только одну конкретную группу задач NP-Complete в своей диссертации и то, как решатели CSP и SAT пытаются разрешить многочисленные случаи этих проблем. У меня также есть примерно год опыта использования CSP и SAT решателей на рабочем месте, но, опять же, это даже близко к вашему 10-летнему опыту в этой области. Ваши "два цента", вероятно, стоят "двух золотых самородков". Один вопрос.
Тайфун платят
1
В своем ответе вы заявляете следующее: «Это неправда, что решатели SAT являются универсально хорошими решателями для любой проблемы, в которую вы их бросаете ....». Удалось ли вам посмотреть на соотношение предложений и переменных, c = m / n, для этих случаев? Другими словами, они были в жесткой области, с = ~ 4,2 или нет? Потому что я испытал то, что при преобразовании экземпляра CSP в экземпляр SAT у вас получается много переменных, и это обычно происходит по этой причине, а не потому, что на самом деле она находится в жесткой области, для решения SAT требуется больше времени. время решить.
Тайфун платят
1
С другой стороны, если вы знаете, что эти случаи оказались в жесткой области SAT, c = ~ 4.2, то могу ли я знать, что это была за проблема в реальной жизни? Мне было бы очень интересно узнать, какие реальные проблемы на самом деле оказываются в сложной области SAT, когда они сводятся к ней. Спасибо
Тайфун Pay
2
Честно говоря, у меня практически нет опыта практического решения SAT. Вся моя настоящая работа была на чисто теоретической стороне этого вопроса. Но как бы то ни было, относительно вашего вопроса: у меня сложилось впечатление, что результаты для случайного k-SAT и плотности предложений (которые вы упоминаете) действительно применимы, только если ваш входной экземпляр является буквально случайной формулой. Также обратите внимание, что ограничение ~ 4.2 применяется только в том случае, если формула 3-SAT, в отличие от формулы CNF смешанной длины.
Магнус Вальстрем
1
И под «проблемами, которые не очень хорошо решаются специалистами по SAT», я в основном имею в виду проблемы, которые считаются действительно неразрешимыми, такие как взлом хорошей криптографии. Тем не менее, существуют также формулы, которые ни один решатель CDCL не сможет решить эффективно из-за теоретико-доказательных нижних оценок, таких как формулы принципа голубиного отверстия. Я видел по крайней мере один разговор с сообщением «Решатели CDCL SAT потерпели неудачу во мне», где небольшое копание показывает, что их проблема кодирования скрывает аспект, похожий на «голубиную дыру» (например, содержащий некоторую вариацию проблемы назначения). К сожалению, я не могу вспомнить детали.
Магнус Вальстрем
15

В CP '12 есть статья « Соотношение мер сложности доказательства и практической твердости SAT », написанная Матти Ярвисало, Арье Мацлиа, Якобом Нордстремом и Станиславом Живным, в которой делается попытка связать твердость или простоту решения определенных формул с помощью решателей CDCL с доказательством разрешения. меры сложности, в частности разрешение пробела пространства. Результаты несколько смешаны, но я думаю, что это шаг в правильном направлении.

Ян Йоханнсен
источник
К сожалению, короткий ответ, по-видимому, заключается в том, что на самом деле нет четкой и убедительной связи с мерами сложности доказательства. Возможно, все еще существуют нетривиальные корреляции, но кажется, что теория слишком чиста, а реальность слишком запутана, чтобы можно было найти действительно хорошее совпадение. Что касается документа «Соотношение доказательных мер сложности», то выяснилось, что более подробные эксперименты дают гораздо более сложную картину с менее четкими выводами - мы надеемся получить полную версию журнала, сообщающую об этом в любое десятилетие, но это сложно Хотя все еще, надеюсь, интересно.
Якоб Нордстрем
15

Я не эксперт в этой области, но я думаю, что случайный материал SAT / фазовый переход более или менее полностью не связан с материалом промышленного / практического применения.

Например, очень хорошие решатели для случайных случаев (такие как https://www.gableske.net/dimetheus ) основаны на методах статистической физики (распространение убеждений и т. Д.), Я полагаю, тогда как очень хорошие «общие» решатели (такие как как http://fmv.jku.at/lingeling/ ) используют несвязанные методы (больше похоже на то, о чем говорил Каве), я верю.

Но, как я уже сказал, возможно, не верьте мне на слово; это исходит от определенного неэксперта.

Райан О'Доннелл
источник
Да. Случайные SAT и промышленные SAT - совершенно разные игры, а используемые методы разные. И, кроме того, если вы хотите решить действительно сложные комбинаторные случаи, тогда все же другие методы более успешны (например, если проблема достаточно сложна, то обучение по пунктам не окупается, за исключением, возможно, очень локально). Но почему-то кажется довольно распространенным заблуждением (по крайней мере, в прикладной части сообщества SAT), что отношение предложений к переменным должно как-то относиться к любому экземпляру CNF SAT, а не только к случайным.
Якоб Нордстрем