Document Type
Conference Proceeding
Publication Date
6-2-2017
Abstract
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.
Recommended Citation
Royer, Melvin, "Axioms: Mathematical and Spiritual: What Says the Parable?" (2017). ACMS Conference Proceedings 2017. 20.
https://pillars.taylor.edu/acms-2017/20
Included in
Applied Mathematics Commons, Computer Sciences Commons, Higher Education Commons, History of Science, Technology, and Medicine Commons, Mathematics Commons, Science and Mathematics Education Commons, Teacher Education and Professional Development Commons