4
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Equations in oligomorphic clones and the Constraint Satisfaction Problem for \(\omega\)-categorical structures

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain non-trivial identity of height one modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the identities of height one (without outer embeddings) satisfied by its polymorphisms clone, together with the natural uniformity on it, being non-trivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that \(\omega\)-categoricity alone is insufficient for this equivalence to hold for a model-complete core. Taking a different approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a system of non-trivial identities of height one, and moreover obtain non-trivial identities of height one for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the existence and uniqueness of the model-complete core of an \(\omega\)-categorical structure.

          Related collections

          Most cited references8

          • Record: found
          • Abstract: not found
          • Article: not found

          Fraïssé Limits, Ramsey Theory, and topological dynamics of automorphism groups

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            A survey of homogeneous structures

              Bookmark
              • Record: found
              • Abstract: not found
              • Book Chapter: not found

              Non-dichotomies in Constraint Satisfaction Complexity

                Bookmark

                Author and article information

                Journal
                2016-12-22
                Article
                1612.07551
                1ac2640a-e4d3-4e37-9c27-ebe43dc9030d

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                25 pages
                cs.LO math.LO

                Theoretical computer science,Logic & Foundation
                Theoretical computer science, Logic & Foundation

                Comments

                Comment on this article