Computer Science – Logic in Computer Science
Scientific paper
2010-05-07
Computer Science
Logic in Computer Science
15 pages; in this version, some editing mistakes in the conclusion have been fixed
Scientific paper
We study techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems. For certain fundamental algebraic structures Delta, we prove definability dichotomy theorems of the following form: for every first-order expansion Gamma of Delta, either Gamma has a quantifier-free Horn definition in Delta, or there is an element d of Gamma such that all non-empty relations in Gamma contain a tuple of the form (d,...,d), or all relations with a first-order definition in Delta have a primitive positive definition in Gamma. The results imply that several families of constraint satisfaction problems exhibit a complexity dichotomy: the problems are in P or NP-hard, depending on the choice of the allowed relations. As concrete examples, we investigate fundamental algebraic constraint satisfaction problems. The first class consists of all first-order expansions of (Q;+). The second class is the affine variant of the first class. In both cases, we obtain full dichotomies by utilising our general methods.
Bodirsky Manuel
Jonsson Peter
Oertzen Timo von
No associations
LandOfFree
Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-222149