Сколько экземпляров 3-SAT является удовлетворительным?

28

Рассмотрим задачу 3-SAT для n переменных. Количество возможных отдельных предложений:

C=2n×2(n1)×2(n2)/3!=4n(n1)(n2)/3.

Количество проблемных экземпляров есть число всех подмножеств множества возможных положений: . Тривиально, для каждого n 3 существует хотя бы один выполнимый экземпляр и один неудовлетворительный экземпляр. Можно ли рассчитать или хотя бы оценить число выполнимых экземпляров для любого данного n?I=2Cn3

Антонио Валерио Мицели-Бароне
источник
См. Также связанный вопрос cstheory.stackexchange.com/q/14953
Саламон
Не могли бы вы объяснить, как получить формулу счета? Где же 3! откуда и т.д?
Ян Кинг Инь
Другой вопрос новичка: если общее количество конфигураций (т. Е. Назначений истинности) равно , это означает, что многие назначения истинности не могут быть выражены ни одним проблемным экземпляром. Насколько мне известно, это противоречит тому, что логические формулы являются полными в том смысле, что они могут выражать любую таблицу истинности. В чем тут подвох? 22n2C
Ян Кинг Инь

Ответы:

27

Долгая история работы над фазовыми переходами в SAT показала, что для любого фиксированного существует порог, параметризованный отношением числа предложений к n, который решает выполнимость. Грубо говоря, если отношение меньше 4,2, то с подавляющей вероятностью экземпляр является выполнимым (и, таким образом, выполнима огромная доля числа экземпляров с этими множеством предложений и переменных). Если соотношение немного выше 4,2, то имеет место обратное - подавляющая часть случаев неудовлетворительна.nn

Ссылок здесь слишком много, чтобы ссылаться на них: одним из источников информации является книга Мезарда и Монтанари . Если у кого-то есть источники для опросов и т. Д. По этой теме, они могут опубликовать его в комментариях или отредактировать этот ответ (я сделаю это CW)

Ссылки:
- Achlioptas обзор
- Где действительно трудные проблемы
- Доработка фазового перехода в комбинаторном поиске

Суреш Венкат
источник
Это очень интересно. Какова "подавляющая вероятность"? Это что-то вроде 75% или 99,9999%?
Филипп Уайт
Я не помню, если честно. он параметризован расстоянием отношения от точки переключения и действует как сигмоид (поэтому он очень быстро увеличивается до 1). Связанные опросы, вероятно, имеют больше деталей
Суреш Венкат
1
k
17

2|C|

2(7/8)|C|

2n|C|=O(n3)

Магнус Вальстрём
источник
3n2n3n2n2n1 < numberofclauses 3n2nтогда эти случаи были либо однозначно удовлетворительными, либо неудовлетворительными. Я не припоминаю вывод для 3-SAT в верхней части моей головы. Хорошо
Тайфун
4

Этот ответ касается только темпов роста числа удовлетворяемых случаев.

AO(nk)kNPP=NP

Мухаммед Аль-Туркистани
источник