Lijie Chen ; Jiatu Li ; Igor C. Oliveira - On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$

lmcs:13450 - Logical Methods in Computer Science, September 10, 2025, Volume 21, Issue 3 - https://doi.org/10.46298/lmcs-21(3:26)2025
On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$Article

Authors: Lijie Chen ; Jiatu Li ; Igor C. Oliveira

    We show that there is a constant $k$ such that Buss's intuitionistic theory $\mathsf{IS}^1_2$ does not prove that SAT requires co-nondeterministic circuits of size at least $n^k$. To our knowledge, this is the first unconditional unprovability result in bounded arithmetic in the context of worst-case fixed-polynomial size circuit lower bounds. We complement this result by showing that the upper bound $\mathsf{NP} \subseteq \mathsf{coNSIZE}[n^k]$ is unprovable in $\mathsf{IS}^1_2$.

    In order to establish our main result, we obtain new unconditional lower bounds against refuters that might be of independent interest. In particular, we show that there is no efficient refuter for the lower bound $\mathsf{NP} \nsubseteq \mathsf{i.o.}\text{-}\mathsf{coNP}/\mathsf{poly}$, addressing in part a question raised by Atserias (2006).


    Volume: Volume 21, Issue 3
    Published on: September 10, 2025
    Accepted on: June 16, 2025
    Submitted on: April 22, 2024
    Keywords: Logic in Computer Science, Computational Complexity

    Consultation statistics

    This page has been seen 528 times.
    This article's PDF has been downloaded 150 times.