Name
Title | ||
|---|---|---|
Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction. |
Abstract | ||
|---|---|---|
We study techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems. For certain basic algebraic structures Δ, we prove definability theorems of the following form: for every first-order expansion Γ of Δ, either Γ has a quantifier-free Horn definition in Δ, or there is an element d of Γ such that all non-empty relations in Γ contain a tuple of the form... |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1093/logcom/exr011 | Journal of Logic and Computation |
Keywords | Field | DocType |
Constraint satisfaction problems,complexity dichotomy,primitive positive definability,linear program feasibility,linear programming | Discrete mathematics,Combinatorics,Algebraic number,Tuple,Algebraic structure,Constraint graph,Algorithm,Constraint satisfaction problem,Complexity of constraint satisfaction,Constraint satisfaction dual problem,Constraint logic programming,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 3 | 0955-792X |
Citations | PageRank | References |
4 | 0.44 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel Bodirsky | 1 | 644 | 54.63 |
| Peter Jonsson | 2 | 23 | 6.80 |
| Timo Von Oertzen | 3 | 71 | 7.84 |