一句话：揭示约束满足问题复杂度层级与有限关系结构上的逻辑紧致性假设层级之间的对应关系。
本文考察约束满足问题（CSP）的复杂度层级与有限关系结构上的逻辑紧致性假设层级之间的对应关系。作者将不同难度的 CSP 与相应的紧致性命题联系起来，比较这些命题在集合论公理系统中的证明强度。结果表明，CSP 越难，其对应的紧致性假设越强：在最顶层，NP-完全的 CSP 对应那些在所有已考察情形中与超滤子公理等价的紧致性假设；在最底层，最简单的 CSP 对应可由 Zermelo-Fraenkel（ZF）公理直接证明的紧致性假设。该工作为 CSP 复杂度分类提供了逻辑与集合论视角，并提示复杂度层级与逻辑紧致性强度之间存在精细对应。
We investigate a correspondence between the complexity hierarchy of constraint satisfaction problems and a hierarchy of logical compactness hypotheses for finite relational structures. It seems that the harder a constraint satisfaction problem is, the stronger the corresponding compactness hypothesis is. At the top level, the NP-complete constraint satisfaction problems correspond to compactness hypotheses that are equivalent to the ultrafilter axiom in all the cases we have investigated. At the bottom level, the simplest constraint satisfaction problems correspond to compactness hypotheses that are readily provable from the axioms of Zermelo and Fraenkel.
@article{paperbot210,
title = {Logical compactness and constraint satisfaction problems},
author = {Danny Rorabaugh and Claude Tardif and David Wehlau},
journal = {Logical Methods in Computer Science},
volume = {Volume 13, Issue 1},
year = {2017},
doi = {10.23638/lmcs-13(1:1)2017}
}