liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Inngår i: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 85, nr 1, s. 188-215Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Springer, 2023. Vol. 85, nr 1, s. 188-215
Emneord [en]
Constraint satisfaction, Infinite domains, Equality languages, Fine-grained complexity, Lower bounds
HSV kategori
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
Swedish Research Council, 2017-04112Swedish Research Council, 2019-03690Tilgjengelig fra: 2023-10-13 Laget: 2023-10-13 Sist oppdatert: 2024-03-14bibliografisk kontrollert

Open Access i DiVA

fulltext(804 kB)197 nedlastinger
Filinformasjon
Fil FULLTEXT03.pdfFilstørrelse 804 kBChecksum SHA-512
a11fe9afb8ab0573e72e17f2fa4dca4c7fe8f49a5e3ea24d96c2d6d42d7024423f38bf5bf2004132a07388654dc5b9f06bd0598ea33250eb06c5c11c2370ff8e
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekstScopus

Person

Jonsson, PeterLagerkvist, Victor

Søk i DiVA

Av forfatter/redaktør
Jonsson, PeterLagerkvist, Victor
Av organisasjonen
I samme tidsskrift
Algorithmica

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 198 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 288 treff
RefereraExporteraLink to record
Permanent link

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