On the Computational Power of Extensional ESO

Abstract

Extensional ESO is a fragment of existential second-order logic (ESO) that captures the following family of problems. Given a fixed ESO sentence $\hat{I}¨$ 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 $\hat{I}¨$, i.e., a structure $\mathbb{B}$ such that $R^{\mathbb{A}}\subseteq R^{\mathbb{B}}$ for every existentially quantified predicate $R$ of $\hat{I}¨$, and $R^{\mathbb{A}}=R^{\mathbb{B}}$ for every non-quantified predicate $R$ of $\hat{I}¨$. In particular, extensional ESO describes all pre-coloured finite-domain constraint satisfaction problems (CSPs). In this paper we study the computational power of extensional ESO; we ask, for which problems in NP is there a polynomial-time equivalent problem in extensional ESO?. One of our main results states that extensional ESO has the same computational power as hereditary first-order logic. We also characterize the computational power of the fragment of extensional ESO with monotone universal first-order part in terms of finitely bounded CSPs. These results suggest a rich computational power of this logic, and we conjecture that extensional ESO captures NP-intermediate problems. We further support this conjecture by showing that extensional ESO can express current candidate NP-intermediate problems such as Graph Isomorphism, and Monotone Dualization (up to polynomial-time equivalence). On the other hand, another main result proves that extensional ESO does not have the full computational power of NP: there are problems in NP that are not polynomial-time equivalent to a problem in extensional ESP (unless E=NE).

For a better streamlined presentation of the first version of arXiv:2411.10860, we split its contents into two papers. This one contains all results on extensional ESO, and we present some new results (Sections 3 and 6)