GMSNP and Finite Structures

Abstract

Given an (infinite) relational structure $\mathbb{S}$, we say that a finite structure $\mathbb{C}$ is a minimal finite factor of $\mathbb{S}$ if for every finite structure $\mathbb{A}$ there is a homomorphism $\mathbb{S}\to \mathbb{A}$ if and only if there is a homomorphism $\mathbb{C}\to \mathbb{A}$. In this brief note we prove that if CSP($\mathbb{S}$) is in GMSNP, then $\mathbb{S}$ has a minimal finite factor $\mathbb{C}$, and moreover, CSP($\mathbb{C}$) reduces in polynomial time to CSP($\mathbb{S}$). We discuss two nice applications of this result. First, we see that if a finite promise constraint satisfaction problem PCSP($\mathbb{A},\mathbb{B}$) has a tractable 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 CSP($\mathbb{G}$) is in GMSNP, then CSP($\mathbb{G}$) in NP-complete, partially answering a question recently asked by Bodirsky and Guzmán-Pro.