Event
Danny Rorabaugh, Queen'S University
Friday, November 4, 2016 15:30to16:30
Burnside Hall
Room 1B23, 805 rue Sherbrooke Ouest, Montreal, QC, H3A 0B9, CA
Bridging logic and constraint satisfaction with relational structures and filters.
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.
This is joint work with Claude Tardif and David Wehlau, arXiv:1609.05221 [math.LO].
This is joint work with Claude Tardif and David Wehlau, arXiv:1609.05221 [math.LO].