2026-07-22T04:54:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22658 2026-04-17T05:31:56Z ddc:004 open_access

Provability of the Circuit Size Hierarchy and Its Consequences Carmosino, Marco Kabanets, Valentine Kolokolova, Antonina C. Oliveira, Igor Tsintsilidas, Dimitrios Bounded Arithmetic Circuit Complexity Hierarchy Theorems The Circuit Size Hierarchy (CSH^a_b) states that if a > b ≥ 1 then the set of functions on n variables computed by Boolean circuits of size n^a is strictly larger than the set of functions computed by circuits of size n^b. This result, which is a cornerstone of circuit complexity theory, follows from the non-constructive proof of the existence of functions of large circuit complexity obtained by Shannon in 1949. Are there more "constructive" proofs of the Circuit Size Hierarchy? Can we quantify this? Motivated by these questions, we investigate the provability of CSH^a_b in theories of bounded arithmetic. Among other contributions, we establish the following results: i) Given any a > b > 1, CSH^a_b is provable in Buss’s theory 𝖳²₂. ii) In contrast, if there are constants a > b > 1 such that CSH^a_b is provable in the theory 𝖳¹₂, then there is a constant ε > 0 such that 𝖯^NP requires non-uniform circuits of size at least n^{1 + ε}. In other words, an improved upper bound on the proof complexity of CSH^a_b would lead to new lower bounds in complexity theory. We complement these results with a proof of the Formula Size Hierarchy (FSH^a_b) in PV₁ with parameters a > 2 and b = 3/2. This is in contrast with typical formalizations of complexity lower bounds in bounded arithmetic, which require APC₁ or stronger theories and are not known to hold even in 𝖳¹₂. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marco Carmosino and Valentine Kabanets and Antonina Kolokolova and Igor C. Oliveira and Dimitrios Tsintsilidas 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.30 urn:nbn:de:0030-drops-226586 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.30 eng https://creativecommons.org/licenses/by/4.0/legalcode