> Detailanzeige

Gillibert, Pierre [VerfasserIn]; Jonušas, Julius [VerfasserIn]; Kompatscher, Michael [VerfasserIn]; Mottet, Antoine [VerfasserIn]; Pinsker, Michael [VerfasserIn] ; Pierre Gillibert and Julius Jonušas and Michael Kompatscher and Antoine Mottet and Michael Pinsker [MitwirkendeR]

Hrushovski’s Encoding and ω-Categorical CSP Monsters

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: E-Artikel; Elektronischer Konferenzbericht; Sonstige Veröffentlichung
  • Titel: Hrushovski’s Encoding and ω-Categorical CSP Monsters
  • Beteiligte: Gillibert, Pierre [VerfasserIn]; Jonušas, Julius [VerfasserIn]; Kompatscher, Michael [VerfasserIn]; Mottet, Antoine [VerfasserIn]; Pinsker, Michael [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.ICALP.2020.131
  • Schlagwörter: pointwise convergence topology ; orbit growth ; ω-categoricity ; polymorphism ; Constraint satisfaction problem ; height 1 identity ; complexity
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: We produce a class of ω-categorical structures with finite signature by applying a model-theoretic construction - a refinement of an encoding due to Hrushosvki - to ω-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate ω-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity, and ω-categorical templates that show that membership in any given complexity class cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of ω-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.
  • Zugangsstatus: Freier Zugang