Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-083 | 18th April 2024 01:32

On the Unprovability of Circuit Size Bounds in Intuitionistic $S^1_2$

RSS-Feed




TR24-083
Authors: Lijie Chen, Jiatu Li, Igor Carboni Oliveira
Publication: 21st April 2024 19:11
Downloads: 288
Keywords: 


Abstract:

We show that there is a constant $k$ such that Buss's intuitionistic theory $\mathbf{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 $\mathbf{NP} \subseteq \mathbf{coNSIZE}[n^k]$ is unprovable in $\mathbf{IS}^1_2$.



ISSN 1433-8092 | Imprint