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 762 times.
This article's PDF has been downloaded 304 times.