Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Abstract

Many natural decision problems can be formulated as constraint satisfaction problems for reducts of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. Our first result is a general polynomial-time reduction from such infinite-domain CSPs to finite-domain CSPs. We use this reduction to obtain new powerful polynomial-time tractability conditions that can be expressed in terms of topological polymorphism clones. Moreover, we study the subclass C of CSPs for structures that are first-order definable over equality with parameters. Also this class C properly extends the class of all finite-domain CSPs. We show that the tractability conjecture for reducts of finitely bounded homogeneous structures is for C equivalent to the finite-domain tractability conjecture.

Details

OriginalspracheEnglisch
TitelProceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016
Herausgeber (Verlag)IEEE, New York [u. a.]
Seiten623-632
Seitenumfang10
ISBN (elektronisch)9781450343916
PublikationsstatusVeröffentlicht - 5 Juli 2016
Peer-Review-StatusJa

Konferenz

Titel31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016
Dauer5 - 8 Juli 2016
StadtNew York
LandUSA/Vereinigte Staaten

Externe IDs

ORCID /0000-0001-8228-3611/work/142241101

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

  • abstract tractability conditions, canonical functions, constraint satisfaction problems