2026-07-22T21:03:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23722 2025-10-27T10:42:50Z ddc:004 open_access

Provably Total Functions in the Polynomial Hierarchy Fleming, Noah Imrek, Deniz Marciot, Christophe TFNP TFPH Proof Complxity Characterizations TFNP studies the complexity of total, verifiable search problems, and represents the first layer of the total function polynomial hierarchy (TFPH). Recently, problems in higher levels of the TFPH have gained significant attention, partly due to their close connection to circuit lower bounds. However, very little is known about the relationships between problems in levels of the hierarchy beyond TFNP. Connections to proof complexity have had an outsized impact on our understanding of the relationships between subclasses of TFNP in the black-box model. Subclasses are characterized by provability in certain proof systems, which has allowed for tools from proof complexity to be applied in order to separate TFNP problems. In this work we begin a systematic study of the relationship between subclasses of total search problems in the polynomial hierarchy and proof systems. We show that, akin to TFNP, reductions to a problem in TFΣ_d are equivalent to proofs of the formulas expressing the totality of the problems in some Σ_d-proof system. Having established this general correspondence, we examine important subclasses of TFPH. We show that reductions to the StrongAvoid problem are equivalent to proofs in a Σ₂-variant of the (unary) Sherali-Adams proof system. As well, we explore the TFPH classes which result from well-studied proof systems, introducing a number of new TFΣ₂ classes which characterize variants of DNF resolution, as well as TFΣ_d classes capturing levels of Σ_d-bounded-depth Frege. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noah Fleming and Deniz Imrek and Christophe Marciot 2025 Is Part Of LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2025.28 urn:nbn:de:0030-drops-237223 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.28 eng https://creativecommons.org/licenses/by/4.0/legalcode