On the Computational Power of Extensional ESO

Extensional ESO is a fragment of existential second-order logic (ESO) that captures the following family of problems. Given a fixed ESO sentence $Ψ$ and an input structure $\mathbb A$ the task if to decide whether there is an extension $\mathbb B$ of $\mathbb A$ that satisfies the first-order part of $Ψ$, i.e., a structure $\mathbb B$ such that $R^{\mathbb A}\subseteq R^{\mathbb B}$ for every existentially quantified predicate $R$ of $Ψ$, and $R^{\mathbb A} = R^{\mathbb B}$ for every non-quantif...