Примеры твердости фазовых переходов

20

Предположим, у нас есть проблема, параметризованная вещественным параметром p, который «легко» решить, когда и «трудно», когда для некоторых значений , . p = p 1 p 0 p 1p=p0p=p1p0p1

Одним из примеров является подсчет спиновых конфигураций на графиках. Считая взвешенные правильные раскраски, независимые множества, эйлеровы подграфы соответствуют функциям разбиения хардкорных моделей, моделей Поттса и Изинга соответственно, которые легко аппроксимировать для «высокой температуры» и трудно для «низкой температуры». Для простого MCMC фазовый переход твердости соответствует точке, в которой время смешивания переходит от полинома к экспоненте ( Martineli, 2006 ).

Другим примером является вывод в вероятностных моделях. Мы «упрощаем» данную модель, взяв , комбинацию с моделью «все переменные независимы». Для проблема тривиальна, для она неразрешима, а порог твердости лежит где-то посередине. Для самого популярного метода вывода проблема становится сложной, когда метод не сходится, и точка, когда это происходит, соответствует фазовому переходу (в физическом смысле) определенного распределения Гиббса ( Tatikonda, 2002 ).p p = 1 p = 01ppp=1p=0

Каковы другие интересные примеры «скачка» твердости при изменении некоторого непрерывного параметра?

Мотивация: увидеть примеры другого «измерения» твердости помимо типа графика или логического типа

Ярослав Булатов
источник
3
Связанный вопрос: скачки твердости в вычислительной сложности . Этот опрос Фридгута также может быть полезен: Охота за острыми порогами .
Каве

Ответы:

18

В стандартном приближении наихудшего случая существует много резких пороговых значений, поскольку коэффициент приближения изменяется.

Например, для 3LIN, удовлетворяющего как можно большему количеству заданных булевых линейных уравнений по 3 переменным каждая, существует простой алгоритм аппроксимации случайного назначения для приближения 1/2, но любое приближение лучше, чем некоторое t = 1/2 + o (1), уже так же сложно, как точное SAT (предположительно, требует экспоненциального времени).

Дана Мошковиц
источник
19

Я не совсем уверен, что это именно та проблема, которую вы искали, но фазовый переход задач NP-Complete является (на данный момент) хорошо известным явлением. См. Статьи Брайана Хейса "Не могу получить никакого удовлетворения" о фазовом переходе 3-SAT и "Самая простая трудная проблема" о фазовом переходе с числовым разделением, для некоторых популярных статей на эту тему.

Selman и Kirkpatrick были первыми, кто численно показал, что фазовый переход для 3-SAT произошел, когда отношение предложений к переменным было около 4,3.

Гент и Уолш были первыми, кто численно показал, что фазовый переход для проблемы разбиения чисел произошел, когда отношение битов к длине списка было около 1. Позже это было доказано аналитически Боргсом, Чейзом и Питтелем .

Командующий продавец, раскраска графика, гамильтонов цикл, помимо прочего, также имеют фазовые переходы для подходящей параметризации создания экземпляра задачи. Я думаю, можно с уверенностью сказать, что общепринято считать, что все задачи NP-Complete демонстрируют фазовый переход для подходящей параметризации.

user834
источник
12

С (некоторыми) моделями шума для квантовых вычислений является пороговое значение для уровня шума, выше которого затворы с шумом могут моделироваться затворами Клиффорда, так что процессы квантовых вычислений становятся эффективно моделируемыми. Для начала, см. Plenio и Virmani, Верхние границы пороговых значений отказоустойчивости шумных квантовых компьютеров на базе Cli- rord (arXiv: 0810.4340v1).

Решаемые модели, подобные этой, информируют нас о вездесущей практической проблеме: для определенной физической квантовой системы, контактирующей с тепловым резервуаром (возможно, при нулевой температуре), уровни шума, связанные с этим тепловым резервуаром, ниже или выше порога для эффективного моделирования с классическим Ресурсы? Если последнее, какие алгоритмы моделирования являются оптимальными?

Джон Сидлес
источник
10

Особенно поразительным примером фазового перехода является ограничение максимальной степени для Точно- SAT (X SAT), в котором каждое предложение содержит ровно различных литералов. Проблема переходит от тривиально простой (всегда выполнимой) к NP-полной, добавляя единицу к связанному параметру.к кkkk

Пусть обозначает наибольшее число, так что любой экземпляр X SAT, в котором любая переменная встречается не более чем в гарантированно будет выполнимым. Если каждая переменная встречается только в одном предложении, то экземпляр является тривиально выполнимым (просто установите для каждой переменной значение, которое делает соответствующий литерал истинным). С другой стороны, совокупность всех предложений по одним и тем же переменным является неудовлетворительной. Отсюда следует, что .k f ( k ) 2 k k 1 f ( k ) < 2 kf(k)kf(k)2kk1f(k)<2k

Экземпляр X SAT имеет естественное (нелогическое) значение, как вопрос о том, существует ли битное сообщение, которое избегает некоторых указанных битных подсообщений. Можно также перемасштабировать параметр естественным образом до , который затем принимает действительное значение в интервале от 0 до 1.n k f ( k ) / 2 kknkf(k)/2k

Все случаи, когда переменные могут встречаться не более раз, все тривиально выполнимы. Однако класс экземпляров, в которых переменные могут встречаться не более раз, уже NP-завершен.f ( k ) + 1f(k)f(k)+1

  • Jan Kratochvíl, Petr Savický и Zsolt Tuza, « Еще одно вхождение переменных делает скачок удовлетворенности с тривиального на NP-полный» , SIAM J. Comput. 22 (1) 203–210, 1993. doi: 10.1137 / 0222015

Интересно также, что для известны довольно узкие границы . Вышеупомянутая статья вывела нижнюю оценку из локальной леммы Ловаша, и неудовлетворительные случаи были явно построены совсем недавно для верхней границы. Короче говоря, .f ( k ) = Θ ( 2 k / k )f(k)f(k)=Θ(2k/k)

Андраш Саламон
источник