Есть 4 различных ограничения, которые мы можем иметь при определении Random K-SAT.
1) Общее количество литералов в заданных предложениях в точности равно K или AT большинству K
2) Данный литерал может использоваться с заменой или без замены в одном и том же предложении (A или A или A)
3) Данная переменная может использоваться с или без замены в том же пункте (A или ~ A или ~ A)
4) Данные пункты могут использоваться с или без замены в заданной формуле.
Каково было бы наиболее «правильное» определение? Каковы плюсы и минусы использования этих разных определений?
cc.complexity-theory
sat
randomness
phase-transition
Тайфун Пей
источник
источник
Ответы:
Две основные модели:
Selman случайная модель - Повторные пункт являются разрешены . Кайл дал эту хорошую ссылку в комментариях к своему ответу, но ошибочно предположил, что модель не допускает повторных предложений. Связанная (немного другая) версия статьи содержит более подробное обсуждение случайной модели в Разделе 3: «Этот метод генерации допускает дублирование предложений в формуле ... Однако, когда N получает большие дубликаты, они станут редкими, потому что мы обычно выберите только линейное количество предложений. "
Эквивалентность мест фазовых переходов :
Однако фазовый переход (порог выполнимости 50%) происходит при одном и том же отношении к переменной, независимо от того, какая из этих моделей выбрана по существу по той причине, что Selman et al. отметил в своей статье.
Пусть обозначает ожидаемое количество идентичных пар предложений в случайном -SAT экземпляре Сельмана. Вероятность того, что данная пара предложений идентична, равна , тогда как общее количество пар предложений равно . По линейности ожидания, .A(n,m,k) (n,m,k) p=1/(2k(nk)) N=(m2) A(n,m,k)=p⋅N=(m2)/2k(nk)
По теореме 3 в [1] доказываемая верхняя граница расположения фазового перехода -SAT с использованием модели Ахлиопты возникает при . Исправив и установив мы получимm = O ( 2 k n ) k ≥ 3 m = O ( 2 k n )k m=O(2kn) k≥3 m=O(2kn)
Тогда, поскольку , , это означает, что в ожидании будет множество повторяющихся предложений вокруг -SAT фазовый переход при генерации случайных формул САТ с использованием модели Сельмана.k≥3 klimn→∞O(n2)/O(nk)=0 k
Бесстыдная самореклама - я кратко обсуждаю эти темы в разделе 4.1 моей магистерской работы .
Случайный QBF
Как выясняется, ситуация гораздо интереснее для случайного QBF. Что касается AFAIK, в первых трех работах по случайному QBF каждая предложена новая случайная модель, критикующая своего предшественника.
Смотрите следующие документы:
источник
[Отредактировано для ясности]
Наиболее широко используемое определение в научной литературе - это определение, которое требует ровно k различных переменных в предложении, а не дублирующих предложений. Если вы ослабите ограничение по отдельным переменным, большая часть существующих исследований не будет иметь смысла для вас, потому что ваши результаты не будут совпадать с их результатами. Хорошо известный фазовый переход sat / unsat будет происходить с другим отношением «условие-переменная» (если этот переход существует вообще), и вы не найдете сложных примеров SAT, которые можно было бы ожидать из литературы.
источник