We develop the novel machinery of smooth approximations, and apply it to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament, various homogeneous graphs including the random graph, and for expansions of the order of the rationals. Apart from obtaining these dichotomy results, we show how our new proof technique allows to unify and significantly simplify the previous results from the literature. For all but the last structure, we moreover characterize those CSPs which are solvable by local consistency methods, again using the same machinery.
翻译:我们开发了光滑近似值的新机制, 并运用它来确认CSP的二分法猜想, 用于随机比赛的一阶降序、 各种同质图表, 包括随机图表, 以及理性顺序的扩展。 除了获得这些二分法结果外, 我们还展示了我们的新验证技术如何允许统一和大大简化文献的先前结果。 除了最后的结构外, 我们还用同样的机器来描述那些可以由本地一致性方法解决的CSP。