Текущие жесткие границы для критической плотности 3-SAT

26

Меня интересует критическая плотность 3-удовлетворяемости (3-SAT) . Предполагается, что такой α существует: если количество случайно сгенерированных 3-SAT-предложений равно ( α + ϵ ) n или более, они почти наверняка неудовлетворительны. (Здесь ϵ - любая малая постоянная, а n - число переменных.) Если число ( α - ϵ ) n или меньше, они почти наверняка выполнимы.αα(α+ϵ)nϵn(αϵ)n

Тезисы Элица Николаева Манева, Алгоритмы распространения убеждений для задач удовлетворения ограничений, ставят проблему с точки зрения распространения убеждений, известного в теории информации. На странице 13 написано если α существует.3.52<α<4.51α

Каковы наиболее известные оценки для ?α

июнь
источник
1
См. Также вопрос cstheory.stackexchange.com/q/1130
Саламон,

Ответы:

17

Несмотря на теорему Фридгута о -SAT, в то время как у нас нет методов, чтобы добраться до пренебрежимо малой ϵ для малых k , кажется более полезным говорить о пороге удовлетворяемости ( α - ϵ ) и пороге неудовлетворенности ( α + ϵ ) как отдельных объектах.kϵkαϵα+ϵ

Известно, что порог неудовлетворенности составляет максимум 4.4898, что является небольшим улучшением по сравнению с тезисом Маневой 2001 года.

Известно, что порог выполнимости составляет не менее 3,52, что не изменилось со времени диссертации Маневой.

  • А. К. Капорис, Л. М. Кироусис, Е. Г. Лалас. Вероятностный анализ алгоритма жадной удовлетворенности , случайных структур и алгоритмов 28 , 2006, 444–480. DOI: 10.1002 / rsa.20104

Эти границы были недавно процитированы Ахлиоптой и Менчака-Мендесом как наиболее известные на сегодняшний день.

  • Д. Ахлиоптас, Р. Менчака-Мендес. Границы неудовлетворенности для случайных CSP из метода энергетической интерполяции , ICALP 2012, LNCS 7391, 1–12. DOI: 10.1007 / 978-3-642-31594-7_1
Андраш Саламон
источник
6

На STOC 2013 принят новый документ на 58 страниц (32 ссылки),

Пройдя порог k-SAT Кожа-Оглан и Константинос Панайоту

что исследует и продвигает область определения точного порога k-SAT, особенно на основе результатов, заимствованных из статистической физики. Из аннотации:

ln212+O(1/k)0.19

К

ВЗН
источник