Rorabaugh, Danny and Tardif, Claude and Wehlau, David - Logical compactness and constraint satisfaction problems

lmcs:2603 - Logical Methods in Computer Science, January 23, 2017, Volume 13, Issue 1
Logical compactness and constraint satisfaction problems

Authors: Rorabaugh, Danny and Tardif, Claude and Wehlau, David

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.


Source : oai:arXiv.org:1609.05221
DOI : 10.23638/LMCS-13(1:1)2017
Volume: Volume 13, Issue 1
Published on: January 23, 2017
Submitted on: January 23, 2017
Keywords: Mathematics - Logic,03E65, 68Q19


Versions

Share

Consultation statistics

This page has been seen 312 times.
This article's PDF has been downloaded 123 times.