Reducts of Finitely Bounded Homogeneous Structures, and...
summary
Claims a conditional P versus NP-complete dichotomy for reducts of finitely bounded homogeneous structures assuming the finite-domain tractability conjecture, and gives a decidable criterion when polymorphism clones admit canonical functions and mseudocyclic polymorphisms. Tools are oligomorphic automorphism groups, the topology of pointwise convergence on clones, continuous clone homomorphisms to the projection clone, and the combinatorial notion of mashups. Shows canonical witnesses yield tractability or NP-hardness in many cases but notes the rational-order reducts (Q) resist the canonical-only method.
AI-written summary · about