The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
By: Manuel Bodirsky , Moritz Jahn , Matěj Konečný and more
Potential Business Impact:
Solves hard math problems about relationships.
Andr\'eka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Hirsch and Cristiani showed that the network satisfaction problem (NSP) for each of these algebras is in P or NP-hard. There are relation algebras with 4 atoms that are not representable, and there are many results in the literature about representations and non-representability of relation algebras with at most 4 atoms. We extend the result of Hirsch and Cristiani to relation algebras with at most 4 atoms: the NSP is always either in P or NP-hard. To this end, we construct universal, fully universal, or even normal representations for these algebras, whenever possible.
Similar Papers
Circular Chromatic Numbers, Balanceability, Relation Algebras, and Network Satisfaction Problems
Combinatorics
Finds patterns in complex networks.
Janus-faces of temporal constraint languages: a dichotomy of expressivity
Logic in Computer Science
Makes solving some tricky computer problems easier.
Janus-faces of temporal constraint languages: a dichotomy of expressivity
Logic in Computer Science
Makes solving some tricky computer puzzles easier.