论文标题
关于约束满意度问题的能力
On amenability of constraint satisfaction problems
论文作者
论文摘要
最近的结果表明，当且仅当它具有可确定的解决方案时，在自然有序上定义的约束满意度问题（CSP）具有解决方案。证明使用拓扑和现代模型理论的高级结果。本文的目的是三倍。 （1）我们给出了简单的纯粹术语证明，并表明不需要拓扑和模型理论的高级结果； （2）我们介绍了陈述的固有表征：“如果CSP具有解决方案，则具有可定义的解决方案”，并在一般直觉的设置理论（3）中进行调查，我们表明，现代模型理论的结果确实需要相反，但是对于“如果可以确定的解决方案），则可以自动又有一个自动的结构。
Recent results show that a constraint satisfaction problem (CSP) defined over rational numbers with their natural ordering has a solution if and only if it has a definable solution. The proof uses advanced results from topology and modern model theory. The aim of this paper is threefold. (1) We give a simple purely-logical proof of the claim and show that the advanced results from topology and model theory are not needed; (2) we introduce an intrinsic characterisation of the statement "definable CSP has a solution iff it has a definable solution" and investigate it in general intuitionistic set theories (3) we show that the results from modern model theory are indeed needed, but for the implication reversed: we prove that "definable CSP has a solution iff it has a definable solution" holds over a countable structure if and only if the automorphism group of the structure is extremely amenable.
