liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Horn versus Full First-order: Complexity Dichotomies in Algebraic Constraint Satisfaction
Ecole Polytechnique, Palaiseau, France.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
University of Virginia, USA.
2012 (English)In: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 22, no 3, 643-660 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2012. Vol. 22, no 3, 643-660 p.
Keyword [en]
Constraint satisfaction problems, complexity dichotomy, primitive positive definability, linear program feasibility, linear programming
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-79513DOI: 10.1093/logcom/exr011OAI: oai:DiVA.org:liu-79513DiVA: diva2:543173
Available from: 2012-08-06 Created: 2012-08-06 Last updated: 2017-12-07

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Jonsson, Peter

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
Software and SystemsThe Institute of Technology
In the same journal
Journal of logic and computation (Print)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 50 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf