Я ищу примеры сложных проблем (в NP или более сложных) из информатики, которые могут быть сведены к моделям физических процессов.
Например, max-2-sat может быть сведен к минимизации энергии в модели Изинга. Я хотел бы найти больше примеров такого типа сокращения.
Подсчет проблем удовлетворения ограничений (#CSP), оценка функций разбиения многих физических моделей, а также многие темы классического моделирования квантовых состояний / цепей - все это принципиально сжимающие тензорные сети, что является # P-полной задачей. Для хорошего обзора см. Следующие документы:
Итай Арад, Зеф Ландау, Квантовые вычисления и оценка тензорных сетей
Цай, Лу, Ся Голографические алгоритмы с захватом спичечных ворот
Особенно смотрите введение последнего для связи с физическими моделями.
Аллан Слай недавно доказал, что MAX-CUT сводится (при рандомизированном восстановлении) к выборке из распределения Гиббса твердого кристаллического газа за пределами фазового перехода единственности на решетке Бете. Менее точные результаты такого рода (когда сокращение сводится к выборке с параметрами, находящимися в пределах области неединственности, а не точно на пороге перехода уникальности), были хорошо известны в течение достаточно долгого времени: см., Например, [LV97] и [DFJ02] ,
Также есть работы Шуха, Сирака и Верстрате, показывающие, что нахождение основных состояний даже 1D-систем с обратным многозонным промежутком сложно с точки зрения NP, даже если нам обещают, что основное состояние является состоянием продукта матрицы - см. Http: // arxiv .org / abs / 0802.3351 . Если я правильно помню, сокращение начинается с произвольного верификатора NP, но не обязательно для конкретной проблемы, такой как MAX-2-SAT.