Разрешимые модели Изинга

Модель Изинга - это распределение бинарных случайных величин (спинов), расположенных в вершинах заданного графа. Мы называем модель Изинга разрешимой, если возможно найти значение статистической суммы (статистический вывод) за полиномиальное время. Разрешимость также подразумевает возможность семплировать случайные конфигурации модели за полиномиальное время. Точный статистический вывод произвольной модели Изинга имел бы значительные последствия для теории вычислений. Поэтому, мы фокусируемся на нахождении и расширении семейств моделей, которые позволяют точный поиск статисти- ческой суммы и семплирование. Мы начинаем с описания эффективных полиномиальных алгоритмов для вывода и семплирования в базовом случае планарных моделей Изинга с нулевым магнитным полем. Затем мы вводим новое семейство моделей Изинга с нулевым магнитным полем на $N$ бинарных спинах, полученное с помощью последовательного ``склеивания'' планарных компонент и компонент размер $O(1)$ вдоль регионов размера максимум 3 вершины в дерево. Полиномиальный алгоритм динамического программирования для точного статистического вывода и семплирования состоит в последовательном применении эффективного (для планарных компонент) или переборного (для компонент размера $O(1)$) вывода и семплирования. В качестве иллюстрации применения нового семейства вычислимых графических моделей, мы, во-первых, предлагаем алгоритм сложности $O(N^\frac32)$ для вывода и семплирования моделей Изинга без магнитного поля, не содержащих минор $K_{33}$ или $K_5$ ——- расширение случая планар- ных моделей Изинга без магнитного поля, которое имеет неограниченный род графа и древесную ширину. Во-вторых, мы эмпирически демонстрируем улучшение качества аппроксимации NP-трудной задачи вывода на решетчатой модели Изинга с ненулевым полем.