liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.ORCID-id: 0000-0002-5288-3330
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
2023 (Engelska)Ingår i: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 85, nr 1, s. 188-215Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We study the fine-grained complexity of NP-complete, infinite-domain constraint satisfaction problems (CSPs) parameterised by a set of first-order definable relations (with equality). Such CSPs are of central importance since they form a subclass of any infinite-domain CSP parameterised by a set of first-order definable relations over a relational structure (possibly containing more than just equality). We prove that under the randomised exponential-time hypothesis it is not possible to find c>1 such that a CSP over an arbitrary finite equality language is solvable in O(cn) time (n is the number of variables). Stronger lower bounds are possible for infinite equality languages where we rule out the existence of 2o(nlog⁡n) time algorithms; a lower bound which also extends to satisfiability modulo theories solving for an arbitrary background theory. Despite these lower bounds we prove that for each c>1 there exists an NP-hard equality CSP solvable in O(cn) time. Lower bounds like these immediately ask for closely matching upper bounds, and we prove that a CSP over a finite equality language is always solvable in O(cn) time for a fixed c, and manage to extend this algorithm to the much broader class of CSPs where constraints are formed by first-order formulas over a unary structure.

Ort, förlag, år, upplaga, sidor
Springer, 2023. Vol. 85, nr 1, s. 188-215
Nyckelord [en]
Constraint satisfaction, Infinite domains, Equality languages, Fine-grained complexity, Lower bounds
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:liu:diva-198447DOI: 10.1007/s00453-022-01017-8ISI: 000839434400001Scopus ID: 2-s2.0-85135869960OAI: oai:DiVA.org:liu-198447DiVA, id: diva2:1804535
Forskningsfinansiär
Vetenskapsrådet, 2017-04112Vetenskapsrådet, 2019-03690Tillgänglig från: 2023-10-13 Skapad: 2023-10-13 Senast uppdaterad: 2024-03-14Bibliografiskt granskad

Open Access i DiVA

fulltext(804 kB)197 nedladdningar
Filinformation
Filnamn FULLTEXT03.pdfFilstorlek 804 kBChecksumma SHA-512
a11fe9afb8ab0573e72e17f2fa4dca4c7fe8f49a5e3ea24d96c2d6d42d7024423f38bf5bf2004132a07388654dc5b9f06bd0598ea33250eb06c5c11c2370ff8e
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Jonsson, PeterLagerkvist, Victor

Sök vidare i DiVA

Av författaren/redaktören
Jonsson, PeterLagerkvist, Victor
Av organisationen
Programvara och systemTekniska fakulteten
I samma tidskrift
Algorithmica
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 198 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 288 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf