Logical compactness and constraint satisfaction problems
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 hypothesi...
Main Authors: | Danny Rorabaugh, Claude Tardif, David Wehlau |
---|---|
Format: | Article |
Language: | English |
Published: |
Logical Methods in Computer Science e.V.
2017-01-01
|
Series: | Logical Methods in Computer Science |
Subjects: | |
Online Access: | https://lmcs.episciences.org/2603/pdf |
Similar Items
-
A topological interpretation of three Leibnizian principles within the functional extensions
by: Marco Forti
Published: (2018-07-01) -
Logical perspectives on the foundations of probability
by: Hosni Hykel, et al.
Published: (2023-06-01) -
Canonical Models and the Complexity of Modal Team Logic
by: Martin Lück
Published: (2019-04-01) -
Feedback computability on Cantor space
by: Nathanael L. Ackerman, et al.
Published: (2019-04-01) -
Foundations of Online Structure Theory II: The Operator Approach
by: Rod Downey, et al.
Published: (2021-07-01)