Я ищу примеры задач, параметризованных числом , где жесткость задачи немонотонна по k . Большинство проблем (по моему опыту) имеют один фазовый переход, например, k- SAT имеет один фазовый переход от k ∈ { 1 , 2 } (где проблема в P) к k ≥ 3 (где проблема NP- полный). Меня интересуют проблемы, в...
Хорошо известной характеристикой экземпляров -SAT является отношение числа предложений m к числу переменных n , т. Е. Частное ρ = m / n . Для каждого k существует пороговое значение α st \ для ρ ≪ α , большинство случаев выполнимо, а для ρ ≫ α большинство случаев неудовлетворительно. Было проведено...
Предположим, у нас есть проблема, параметризованная вещественным параметром p, который «легко» решить, когда и «трудно», когда для некоторых значений , . p = p 1 p 0 p 1p=p0p=p0p=p_0p=p1p=p1p=p_1п0p0p_0п1p1p_1 Одним из примеров является подсчет спиновых конфигураций на графиках. Считая взвешенные...
Хорошо известно, что во многих NP-полных задачах наблюдается фазовый переход. Я заинтересован в фазовом переходе в отношении локализации на языке, а не в сложности ввода относительно алгоритма. Чтобы сделать понятие однозначным, давайте формально определим его следующим образом. Язык LLL...
Критическое отношение предложений к переменным для случайных 3-SAT составляет более 3 и менее 6 и, как представляется, обычно описывается как «около 4,2» или «около 4,25». Mezard, Parisi и Zecchina доказывают (в физическом смысле), что критическое отношение составляет 4,256, тогда как первый и...
Есть 4 различных ограничения, которые мы можем иметь при определении Random K-SAT. 1) Общее количество литералов в заданных предложениях в точности равно K или AT большинству K 2) Данный литерал может использоваться с заменой или без замены в одном и том же предложении (A или A или A) 3) Данная...
Что известно о фазовом переходе в задачах # P-Complete? В частности, существует ли другой фазовый переход для # DNF-k-SAT и # CNF-k-SAT? Обновление: Как мы знаем, в Random k-SAT есть фазовый переход, где решение проблемы переходит от простого к сложному и снова к легкому. Я хотел бы знать,...
Я хотел бы знать текущее состояние фазового перехода для случайных k-sat, учитывая n переменных и m предложений, что является наиболее известным c = m / n для верхней и нижней...