Рассмотрим задачу 3-SAT для n переменных. Количество возможных отдельных предложений:
Количество проблемных экземпляров есть число всех подмножеств множества возможных положений: . Тривиально, для каждого n ≥ 3 существует хотя бы один выполнимый экземпляр и один неудовлетворительный экземпляр. Можно ли рассчитать или хотя бы оценить число выполнимых экземпляров для любого данного n?
cc.complexity-theory
sat
Антонио Валерио Мицели-Бароне
источник
источник
Ответы:
Долгая история работы над фазовыми переходами в SAT показала, что для любого фиксированного существует порог, параметризованный отношением числа предложений к n, который решает выполнимость. Грубо говоря, если отношение меньше 4,2, то с подавляющей вероятностью экземпляр является выполнимым (и, таким образом, выполнима огромная доля числа экземпляров с этими множеством предложений и переменных). Если соотношение немного выше 4,2, то имеет место обратное - подавляющая часть случаев неудовлетворительна.n n
Ссылок здесь слишком много, чтобы ссылаться на них: одним из источников информации является книга Мезарда и Монтанари . Если у кого-то есть источники для опросов и т. Д. По этой теме, они могут опубликовать его в комментариях или отредактировать этот ответ (я сделаю это CW)
Ссылки:
- Achlioptas обзор
- Где действительно трудные проблемы
- Доработка фазового перехода в комбинаторном поиске
источник
источник
Этот ответ касается только темпов роста числа удовлетворяемых случаев.
источник