Меня интересует критическая плотность 3-удовлетворяемости (3-SAT) . Предполагается, что такой α существует: если количество случайно сгенерированных 3-SAT-предложений равно ( α + ϵ ) n или более, они почти наверняка неудовлетворительны. (Здесь ϵ - любая малая постоянная, а n - число переменных.) Если число ( α - ϵ ) n или меньше, они почти наверняка выполнимы.
Тезисы Элица Николаева Манева, Алгоритмы распространения убеждений для задач удовлетворения ограничений, ставят проблему с точки зрения распространения убеждений, известного в теории информации. На странице 13 написано если α существует.
Каковы наиболее известные оценки для ?
Ответы:
Несмотря на теорему Фридгута о -SAT, в то время как у нас нет методов, чтобы добраться до пренебрежимо малой ϵ для малых k , кажется более полезным говорить о пороге удовлетворяемости ( α - ϵ ) и пороге неудовлетворенности ( α + ϵ ) как отдельных объектах.k ϵ k α−ϵ α+ϵ
Известно, что порог неудовлетворенности составляет максимум 4.4898, что является небольшим улучшением по сравнению с тезисом Маневой 2001 года.
Известно, что порог выполнимости составляет не менее 3,52, что не изменилось со времени диссертации Маневой.
Эти границы были недавно процитированы Ахлиоптой и Менчака-Мендесом как наиболее известные на сегодняшний день.
источник
На STOC 2013 принят новый документ на 58 страниц (32 ссылки),
что исследует и продвигает область определения точного порога k-SAT, особенно на основе результатов, заимствованных из статистической физики. Из аннотации:
источник