| Summary: | 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.
|
|---|