Сложность задачи удовлетворения ограничениям и её вариаций

Многие задачи, такие как раскраска графа или решение систем линейных уравнений, могут быть представлены как задачи удовлетворения ограничениям для какого-то языка допустимых ограничений. При этом некоторые из этих задач решаются за полиномиальное время, а некоторые являются NP-полными. В 2017 году сложность задачи удовлетворения ограничениям была описана для любого языка ограничений, но осталось много вариаций этой задачи, для которых сложность по-прежнему неизвестна. Например, можно разрешить кроме квантора существования использовать квантор всеобщности или потребовать, чтобы найденное решение было сюръективным или сбалансированным. Также можно потребовать, чтобы входные данные удовлетворяли какому-то наперед заданному условию, как если нам надо покрасить граф в 100 цветов, если известно, что его можно покрасить в 3 цвета. В работе мы обсудим как обычную задачу удовлетворения ограничениям, так и сложность этих и некоторых других вариаций и обобщений этой задачи.