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
Tractability conditions for numeric CSPs
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Univ Paris Est Marne la Vallee, France.
2018 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 715, p. 21-34Article in journal (Refereed) Published
Abstract [en]

The computational complexity of the constraint satisfaction problem (CSP) with semilinear relations over the reals has gained recent attraction. As a result, its complexity is known for all finite sets of semilinear relations containing the relation R+ = {(x, y, z) is an element of R-3 vertical bar x + y = z}. We consider larger and more expressive classes of relations such as semialgebraic and o-minimal relations. We present a general result for characterising computationally hard fragments and, under certain side conditions, this result implies that polynomial-time solvable fragments are only to be found within two limited families of sets of relations. In the setting of semialgebraic relation, our result takes on a simplified form and we provide a full complexity classification for constraint languages that consist of algebraic varieties. Full classifications like the one obtained here for algebraic varieties or the one for semilinear relations appear to be rare and we discuss several barriers for obtaining further such results. These barriers have strong connections with well-known open problems concerning the complexity of various restrictions of convex programming. (c) 2018 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
ELSEVIER SCIENCE BV , 2018. Vol. 715, p. 21-34
Keywords [en]
Constraint satisfaction problem; Semialgebraic constraint; o-minimality; Algebraic variety; Computational complexity
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-145739DOI: 10.1016/j.tcs.2018.01.013ISI: 000426222500002OAI: oai:DiVA.org:liu-145739DiVA, id: diva2:1192535
Note

Funding Agencies|Swedish Research Council (VR) [621-2012-3239]

Available from: 2018-03-22 Created: 2018-03-22 Last updated: 2018-03-22

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Theoretical Computer Science
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 83 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