Containment for Guarded Monotone Strict NP

19 mai 2025

Alexey Barsukov (Charles University)

Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. The talk will be about the meta-problem of containment for the former logic. While being undecidable for many classes of problems (e.g., Datalog, SNP, first-order) it remains to be decidable for GMSNP. The complexity of the problem is 2NEXPTIME-complete — the same as for MMSNP. In my talk, I will show some examples of GMSNP problems and discuss the methods arising from model and Ramsey theories that are used in order to characterise the containment.