2026-07-20T14:23:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26807 2026-07-09T11:31:08Z ddc:004 open_access

On the Computational Power of Extensional ESO Bodirsky, Manuel Guzmán-Pro, Santiago Existential second-order logic constraint satisfaction problem complexity classification Hereditary first-order logic NP-intermediate problems 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 A the task is to decide whether there is an extension B of A that satisfies the first-order part of Ψ, i.e., a structure B such that R^A ⊆ R^B for every existentially quantified predicate R of Ψ, and R^A = R^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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Santiago Guzmán-Pro 2026 Is Part Of LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.LICS.2026.20 urn:nbn:de:0030-drops-268073 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.20 eng https://creativecommons.org/licenses/by/4.0/legalcode