Search Results

Documents authored by Kirn, Jeremy C.

Document
DOI: 10.4230/LIPIcs.MFCS.2026.63
On Equivalent Characterizations of the Polynomial Hierarchy in Abstract Models of Computation

Authors: Jeremy C. Kirn, Lucas Meijer, Tillmann Miltzow, and Hans L. Bodlaender

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
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.
Cite as

Jeremy C. Kirn, Lucas Meijer, Tillmann Miltzow, and Hans L. Bodlaender. On Equivalent Characterizations of the Polynomial Hierarchy in Abstract Models of Computation. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kirn_et_al:LIPIcs.MFCS.2026.63,
  author =	{Kirn, Jeremy C. and Meijer, Lucas and Miltzow, Tillmann and Bodlaender, Hans L.},
  title =	{{On Equivalent Characterizations of the Polynomial Hierarchy in Abstract Models of Computation}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{63:1--63:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.63},
  URN =		{urn:nbn:de:0030-drops-274450},
  doi =		{10.4230/LIPIcs.MFCS.2026.63},
  annote =	{Keywords: 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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact