Some Problems not Definable Using Structure Homomorphisms

Abstract

We exhibit some problems definable in Feder and Vardi’s logic \(MMSNP\) that are not in the class \(CSP\) of constraint satisfaction problems. Whilst some of these problems have previously been shown to be in \(MMSNP\) (that is, definable in \(MMSNP\)) but not in \(CSP\), existing proofs are probabilistic in nature. We provide explicit combinatorial constructions to prove that these problems are not in \(CSP\) and we use these constructions to exhibit yet more problems in \(MMSNP\) that are not in \(CSP\).