We consider CSPs whose template can be defined in an infinite “ground structure” with a high degree of symmetry (in the form of homogeneity) and a certain finite presentation (finite boundedness). For example, the ground structure can be the order of the rationals, leading to Temporal CSPs, or the random graph, which gives rise to so-called Graph-SAT problems. Such CSPs are always in NP, include all finite-domain CSPs as well as many additional natural problems, and there is an open dichotomy conjecture extending the one for finite templates.
The general algebraic approach to finite domain CSPs via polymorphisms also works in this setting, and the most sensible approach to the conjecture is to try to reduce it to the finite case. To this end, one associates certain finite algebras to a CSP template, and hopes to extract from them sufficient information about the complexity of the CSP. In most successful confirmations of instances of the conjecture so far, this was done somewhat non-systematically, leading to long proofs of ad hoc arguments. The novel Theory of Smooth Approximations intends to provide a uniform way of relating the associated finite algebras with the structure of the CSP template and consequently its computational complexity. Applying this method, all previous results in the literature can be reproven much more smoothly; moreover, the method allows, for the first time, for a systematic investigation of local consistency methods in this setting.
This is joint work with Antoine Mottet.