Homomorphism problems in the infinite context

20.04.2023 15:00 - 15:50

Z. Vidnyánszky (Eötvös Loránd U, HU)

The CSP dichotomy of Bulatov and Zhuk is a celebrated theorem of computer science: it states that given a finite structure \(H\), deciding whether a structure \(G\) admits a homomorphism to \(G\) is either easy (in P) or hard (NP-complete). We will discuss two infinitary versions of this theorem. First, following Thornton, in the Borel con ext. Here a striking difference from the finite world emerges: we will show that solving linear equations over a finite field is already hard (\(\Sigma^1_2\)-complete). Second, assuming only ZF, we will consider the relationship of the \(H\)-compactness properties, that is, the statement that for every \(G\) if every finite substructure of \(G\) admits a homomorphism to \(H\) then so is \(G\). Here we show that there exists a model \(M\) of ZF, such that \(M \models H\)-compactness iff the \(H\)-homomorphism problem is easy.




HS 11, 2. OG, OMP 1