2024/08/23 by Peter Jönsson, Victor Lagerkvist, Jonsson, Peter +3
Computer Science · #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2408.12909
openalex publication_date 2024/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The constraint satisfaction problem asks to decide if a set of constraints over a relational structure A is satisfiable (CSP(A)). We consider CSP(A ∪ B) where A is a structure and B is an alien structure, and analyse its (parameterized) complexity when at most k alien constraints are allowed. We establish connections and obtain transferable complexity results to several well-studied problems that previously escaped classification attempts. Our novel approach, utilizing logical and algebraic methods, yields an FPT versus pNP dichotomy for arbitrary finite structures and sharper dichotomies for Boolean structures and first-order reducts of (ℕ,=) (equality CSPs), together with many partial results for general ω-categorical structures.