GMSNP and Finite Structures

Given an (infinite) relational structure \(\mathbb {S}\) , we say that a finite structure \(\mathbb {C}\) is a smallest finite factor of \(\mathbb {S}\) if for every finite structure \(\mathbb {A}\) there is a homomorphism \(\mathbb {S}\rightarrow \mathbb {A}\) if and only if there is a homomorphism \(\mathbb {C}\rightarrow \mathbb {A}\) . In this brief note we prove that if \(\operatorname{CSP}(\mathbb {S})\) is in \(\operatorname{GMSNP}\) , then \(\mathbb {S}\) has a smallest finite factor \(\mathbb {C}\) , and moreover, \(\operatorname{CSP}(\mathbb {C})\) reduces in polynomial time to \(\operatorname{CSP}(\mathbb {S})\) . We discuss two nice applications of this result. First, we see that if a finite promise constraint satisfaction problem \(\operatorname{PCSP}(\mathbb {A},\mathbb {B})\) has a tractable \(\operatorname{GMSNP}\) sandwich, then it has a tractable finite sandwich. We also show that if \(\mathbb {G}\) is a non-bipartite (possibly infinite) graph with finite chromatic number, and \(\operatorname{CSP}(\mathbb {G})\) is in \(\operatorname{GMSNP}\) , then \(\operatorname{CSP}(\mathbb {G})\) in \(\operatorname{NP}\) -complete, partially answering a question recently asked by Bodirsky and Guzmán-Pro.