Document Type

Conference Proceeding

Publication Date



Relational structure A is compact provided for any structure Jffi of the same signature, if every finite substructure of Jffi has a homomorphism to A then so does Jffi. The Constraint Satisfaction Problem (CSP) for A is the computational problem of determining whether finite structures have homomorphisms into A. We explore a connection between the hierarchy of logical axioms and the complexity hierarchy of CSPs: It appears that the complexity of CSP for A corresponds to the strength of the axiom "A is compact". At the top, the statement "K3 is compacts" is logically equivalent to the compactness theorem. Thus the compactness of K3 implies the compactness of all finite relational structures. Moreover, the CSP for K3 is NP-complete. At the bottom are width-one structures; these are provably complete from ZF and their corresponding CPSs are polynomial-time solvable.


To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.