2026-08-21T18:34:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27445 2026-08-21T14:42:40Z ddc:004 open_access

On Equivalent Characterizations of the Polynomial Hierarchy in Abstract Models of Computation Kirn, Jeremy C. Meijer, Lucas Miltzow, Tillmann Bodlaender, Hans L. Machines over a first-order structure BSS machines Cook Levin Fagin NP existential theory of the reals polynomial hierarchy metafinite model theory descriptive complexity oracles We investigate machine models similar to Turing machines that are augmented with the operations of a first-order structure ℛ, and we show that under weak conditions on ℛ, the complexity class Σ_kℛ may be characterized in four equivalent ways: (1) by polynomial-time algorithms implemented on ℛ-machines together with witness strings, (2) by the Σ_k ℛ-complete problem Σ_k SAT(ℛ), (3) by k-th existential fragment second-order metafinite logic over ℛ via descriptive complexity, and (4) via oracles. By characterizing Σ_k ℛ in these four ways, we extend previous work and embed it in one coherent framework. In addition, we derive similar results for ∃_k ℛ, the constant-free Boolean part of Σ_k ℛ, by showing that ∃_k ℛ may be characterized in four analogous ways. Some conditions on ℛ must be assumed in order to achieve the above quaternity because there are infinite-vocabulary structures for which NP(ℛ) = Σ₁ ℛ does not have a complete problem. Surprisingly, even in these cases, we show that NP(ℛ) does have a characterization in terms of existential second-order metafinite logic, suggesting that descriptive complexity theory is well suited to working with infinite-vocabulary structures, such as real vector spaces. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeremy C. Kirn and Lucas Meijer and Tillmann Miltzow and Hans L. Bodlaender 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.63 urn:nbn:de:0030-drops-274450 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.63 eng https://creativecommons.org/licenses/by/4.0/legalcode