On the Computational Power of Extensional ESO

Manuel Bodirsky, Santiago Guzmán Pro

Extensional ESO is a fragment of existential second-order logic (ESO) that captures the following family of problems. Given a fixed ESO sentence $\Psi$ and an input structure $\mathbb…