Details

Autor(en) / Beteiligte

• Jonsson, Peter
• Lagerkvist, Victor

Titel

General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs

Ist Teil von

• Algorithmica, 2023, Vol.85 (1), p.188-215

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2023

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We study the fine-grained complexity of NP-complete, infinite-domain constraint satisfaction problems (CSPs) parameterised by a set of first-order definable relations (with equality). Such CSPs are of central importance since they form a subclass of any infinite-domain CSP parameterised by a set of first-order definable relations over a relational structure (possibly containing more than just equality). We prove that under the randomised exponential-time hypothesis it is not possible to find c > 1 such that a CSP over an arbitrary finite equality language is solvable in O ( c n ) time ( n is the number of variables). Stronger lower bounds are possible for infinite equality languages where we rule out the existence of 2 o ( n log n ) time algorithms; a lower bound which also extends to satisfiability modulo theories solving for an arbitrary background theory. Despite these lower bounds we prove that for each c > 1 there exists an NP-hard equality CSP solvable in O ( c n ) time. Lower bounds like these immediately ask for closely matching upper bounds, and we prove that a CSP over a finite equality language is always solvable in O ( c n ) time for a fixed c , and manage to extend this algorithm to the much broader class of CSPs where constraints are formed by first-order formulas over a unary structure.