Предположим, у нас есть проблема, параметризованная вещественным параметром p, который «легко» решить, когда и «трудно», когда для некоторых значений , . p = p 1 p 0 p 1
Одним из примеров является подсчет спиновых конфигураций на графиках. Считая взвешенные правильные раскраски, независимые множества, эйлеровы подграфы соответствуют функциям разбиения хардкорных моделей, моделей Поттса и Изинга соответственно, которые легко аппроксимировать для «высокой температуры» и трудно для «низкой температуры». Для простого MCMC фазовый переход твердости соответствует точке, в которой время смешивания переходит от полинома к экспоненте ( Martineli, 2006 ).
Другим примером является вывод в вероятностных моделях. Мы «упрощаем» данную модель, взяв , комбинацию с моделью «все переменные независимы». Для проблема тривиальна, для она неразрешима, а порог твердости лежит где-то посередине. Для самого популярного метода вывода проблема становится сложной, когда метод не сходится, и точка, когда это происходит, соответствует фазовому переходу (в физическом смысле) определенного распределения Гиббса ( Tatikonda, 2002 ).p p = 1 p = 0
Каковы другие интересные примеры «скачка» твердости при изменении некоторого непрерывного параметра?
Мотивация: увидеть примеры другого «измерения» твердости помимо типа графика или логического типа
Ответы:
В стандартном приближении наихудшего случая существует много резких пороговых значений, поскольку коэффициент приближения изменяется.
Например, для 3LIN, удовлетворяющего как можно большему количеству заданных булевых линейных уравнений по 3 переменным каждая, существует простой алгоритм аппроксимации случайного назначения для приближения 1/2, но любое приближение лучше, чем некоторое t = 1/2 + o (1), уже так же сложно, как точное SAT (предположительно, требует экспоненциального времени).
источник
Я не совсем уверен, что это именно та проблема, которую вы искали, но фазовый переход задач NP-Complete является (на данный момент) хорошо известным явлением. См. Статьи Брайана Хейса "Не могу получить никакого удовлетворения" о фазовом переходе 3-SAT и "Самая простая трудная проблема" о фазовом переходе с числовым разделением, для некоторых популярных статей на эту тему.
Selman и Kirkpatrick были первыми, кто численно показал, что фазовый переход для 3-SAT произошел, когда отношение предложений к переменным было около 4,3.
Гент и Уолш были первыми, кто численно показал, что фазовый переход для проблемы разбиения чисел произошел, когда отношение битов к длине списка было около 1. Позже это было доказано аналитически Боргсом, Чейзом и Питтелем .
Командующий продавец, раскраска графика, гамильтонов цикл, помимо прочего, также имеют фазовые переходы для подходящей параметризации создания экземпляра задачи. Я думаю, можно с уверенностью сказать, что общепринято считать, что все задачи NP-Complete демонстрируют фазовый переход для подходящей параметризации.
источник
С (некоторыми) моделями шума для квантовых вычислений является пороговое значение для уровня шума, выше которого затворы с шумом могут моделироваться затворами Клиффорда, так что процессы квантовых вычислений становятся эффективно моделируемыми. Для начала, см. Plenio и Virmani, Верхние границы пороговых значений отказоустойчивости шумных квантовых компьютеров на базе Cli- rord (arXiv: 0810.4340v1).
Решаемые модели, подобные этой, информируют нас о вездесущей практической проблеме: для определенной физической квантовой системы, контактирующей с тепловым резервуаром (возможно, при нулевой температуре), уровни шума, связанные с этим тепловым резервуаром, ниже или выше порога для эффективного моделирования с классическим Ресурсы? Если последнее, какие алгоритмы моделирования являются оптимальными?
источник
Особенно поразительным примером фазового перехода является ограничение максимальной степени для Точно- SAT (X SAT), в котором каждое предложение содержит ровно различных литералов. Проблема переходит от тривиально простой (всегда выполнимой) к NP-полной, добавляя единицу к связанному параметру.к кk k k
Пусть обозначает наибольшее число, так что любой экземпляр X SAT, в котором любая переменная встречается не более чем в гарантированно будет выполнимым. Если каждая переменная встречается только в одном предложении, то экземпляр является тривиально выполнимым (просто установите для каждой переменной значение, которое делает соответствующий литерал истинным). С другой стороны, совокупность всех предложений по одним и тем же переменным является неудовлетворительной. Отсюда следует, что .k f ( k ) 2 k k 1 ≤ f ( k ) < 2 kf(k) k f(k) 2k k 1≤f(k)<2k
Экземпляр X SAT имеет естественное (нелогическое) значение, как вопрос о том, существует ли битное сообщение, которое избегает некоторых указанных битных подсообщений. Можно также перемасштабировать параметр естественным образом до , который затем принимает действительное значение в интервале от 0 до 1.n k f ( k ) / 2 kk n k f(k)/2k
Все случаи, когда переменные могут встречаться не более раз, все тривиально выполнимы. Однако класс экземпляров, в которых переменные могут встречаться не более раз, уже NP-завершен.f ( k ) + 1f(k) f(k)+1
Интересно также, что для известны довольно узкие границы . Вышеупомянутая статья вывела нижнюю оценку из локальной леммы Ловаша, и неудовлетворительные случаи были явно построены совсем недавно для верхней границы. Короче говоря, .f ( k ) = Θ ( 2 k / k )f(k) f(k)=Θ(2k/k)
источник