Сложность задач о подсчете числа решений

Abstract

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

The Constraint Satisfaction Problem (CSP) and the Counting Constraint Satisfaction Problem (#CSP) provide a framework that makes it possible to represent in a generic way a wide variety of problems arising in various areas from mathematical logic to statistical physics. In this paper, we give a concise survey of recent results on the complexity of the #CSP, and particularly those obtained by the algebraic approach to constraint problems.