Меня интересует критическая плотность 3-удовлетворяемости (3-SAT) . Предполагается, что такой α существует: если количество случайно сгенерированных 3-SAT-предложений равно ( α + ϵ ) n или более, они почти наверняка неудовлетворительны. (Здесь ϵ - любая малая постоянная, а n - число переменных.)...
Хорошо известной характеристикой экземпляров -SAT является отношение числа предложений m к числу переменных n , т. Е. Частное ρ = m / n . Для каждого k существует пороговое значение α st \ для ρ ≪ α , большинство случаев выполнимо, а для ρ ≫ α большинство случаев неудовлетворительно. Было проведено...
Была ли проделана какая-либо работа над тем, как сложность случайных экземпляров # 2-SAT зависит от плотности предложения? То есть: как изменяется сложность подсчета удовлетворяющих решений для случайно сгенерированного экземпляра 2-SAT , когда меняется плотность предложений? В частности, известны...
Хорошо известно, что случайные формулы -CNF над n переменными с предложениями c n являются неудовлетворительными (т.е. являются противоречиями) с большой вероятностью для достаточно большой постоянной c . Таким образом, случайные формулы k- CNF (для достаточно больших c ) представляют собой...
Критическое отношение предложений к переменным для случайных 3-SAT составляет более 3 и менее 6 и, как представляется, обычно описывается как «около 4,2» или «около 4,25». Mezard, Parisi и Zecchina доказывают (в физическом смысле), что критическое отношение составляет 4,256, тогда как первый и...
В этой недавней статье FOCS2013 « Сильные черные ходы к SAT ограниченной длины дерева», составленной Gaspers и Szeider, говорится о связи между шириной дерева графика предложения SAT и твердостью экземпляра. Для случайных 3-SAT, то есть 3-SAT экземпляров, выбранных случайным образом, какова...