Тавтологии / противоречия в среднем случае за пределами случайной модели k-CNF

16

Хорошо известно, что случайные формулы -CNF над n переменными с предложениями c n являются неудовлетворительными (т.е. являются противоречиями) с большой вероятностью для достаточно большой постоянной c . Таким образом, случайные формулы k- CNF (для достаточно больших c ) представляют собой естественное распределение по неудовлетворительным булевым формулам (или двойственно, по тавтологиям, т.е. отрицаниям противоречий). Это распределение было тщательно изучено.kncnckc

Мой вопрос заключается в следующем : существуют ли какие-либо другие установленные распределения пропозициональных тавтологий или противоречий, которые можно рассматривать как захват «среднего случая» тавтологий или неудовлетворительных формул? Эти распределения интенсивно изучались?

cc.complexity-theory reference-request lo.logic sat random-k-sat Иддо Цамерет
источник
1
@Iddo Тавтологии не существуют в «истинной» модели CNF, потому что в противном случае вам понадобится литерал и его дополнение в том же пункте .... Тавтологии не интересны для изучения в CNF.
Tayfun Pay
1
@ Пей, отрицание неудовлетворительной формулы, очевидно, тавтология. Следовательно, мы можем рассматривать случайные значения k-CNF как распределение по тавтологиям (когда отношение предложения к переменной достаточно велико и когда существует вероятность o (1) для выполнимости k-CNF).
Иддо Цамерет
1
Я думаю, что Тайфун прав. Вы должны говорить о том, что формулы CNF являются неудовлетворительными, а формулы DNF - тавтологиями. В текущем вопросе вы смешиваете два.
Tsuyoshi Ito
1
Это мой последний комментарий по этому вопросу: я не знаю, почему вы настаиваете на сохранении слова «тавтологии», что, как объяснил Тайфун, явно неверно. Но я в порядке, если вы не хотите включать комментарии других людей, чтобы улучшить формулировку вашего вопроса.
Tsuyoshi Ito
3
Я предпочитаю оставить в названии термин «тавтологии», потому что я спрашиваю о распределении тавтологий или противоречий, и вопрос формулируется соответствующим образом.
Иддо Цамерет

Ответы:

4

У Пола Бима есть две работы (с различными соавторами), в которых изучается сложность разрешения некоторых распределений случайных формул. Эти формулы возникают путем выражения свойств, таких как k-окрашиваемость или наличие независимых наборов размера k, случайных графов из обычного распределенияграмм(N,п), Вот ссылки:

Пол Бим, Рассел Импальяццо и Ашиш Сабхарвал. Сложность разрешения независимых множеств и покрытий вершин в случайных графах. Вычислительная сложность, 16 (3): 245-297, 2007.

Пол Бим, Джо Калберсон, Дэвид Митчелл и Кристофер Мур. Сложность разрешения случайного графа k-окрашиваемости. Дискретная прикладная математика, 153: 25-47, 2005.

Ян Йоханнсен
источник