On the Computational Power of Extensional ESO
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918196876935168 |
|---|---|
| author | Bodirsky, Manuel Pro, Santiago Guzmán |
| author_facet | Bodirsky, Manuel Pro, Santiago Guzmán |
| contents | 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-quantified predicate $R$ of $Ψ$. 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08515 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Computational Power of Extensional ESO Bodirsky, Manuel Pro, Santiago Guzmán Logic Computational Complexity Discrete Mathematics Logic in Computer Science 03B16, 03B70, 03C13 F.1.3; F.4.1 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-quantified predicate $R$ of $Ψ$. 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). |
| title | On the Computational Power of Extensional ESO |
| topic | Logic Computational Complexity Discrete Mathematics Logic in Computer Science 03B16, 03B70, 03C13 F.1.3; F.4.1 |
| url | https://arxiv.org/abs/2511.08515 |