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
An initial study of time complexity in infinite-domain constraint satisfaction
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Technical University of Dresden, Germany.
2017 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 245, 115-133 p.Article in journal (Refereed) Published
Abstract [en]

The constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science and artificial intelligence. For infinite-domain CSPs, there are many results separating tractable and NP-hard cases while upper and lower bounds on the time complexity of hard cases are virtually unexplored, Hence, we initiate a study of the worst-case time complexity of such CSPs, We analyze backtracking algorithms and determine upper bounds on their time complexity. We present asymptotically faster algorithms based on enumeration techniques and we show that these algorithms are applicable to well-studied problems in, for instance, temporal reasoning. Finally, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that certain complexity-theoretic assumptions hold. The gap between upper and lower bounds is in many cases surprisingly small, which suggests that our upper bounds cannot be significantly improved. (C) 2017 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
ELSEVIER SCIENCE BV , 2017. Vol. 245, 115-133 p.
Keyword [en]
Constraint satisfaction; Infinite domain; Time complexity
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-136570DOI: 10.1016/j.artint.2017.01.005ISI: 000395612800005OAI: oai:DiVA.org:liu-136570DiVA: diva2:1090308
Note

Funding Agencies|Swedish Research Council [621-2012-3239]; National Graduate School in Computer Science (CUGS), Sweden; DFG project "Homogene Strukturen, Bedingungserfullungsprobleme, and topologische Klone" [622397]

Available from: 2017-04-24 Created: 2017-04-24 Last updated: 2017-05-19

Open Access in DiVA

The full text will be freely available from 2019-01-27 14:26
Available from 2019-01-27 14:26

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
Artificial Intelligence
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 24 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