On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsfS^1_2$
<|reference_start|>On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsfS^1_2$: 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$.<|reference_end|>
@article{chen2024on,
    title={On the Unprovability of Circuit Size Bounds in Intuitionistic
  $\mathsf{S}^1_2$},
    author={Lijie Chen, Jiatu Li, Igor C. Oliveira},
    journal={arXiv preprint arXiv:2404.11841},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.11841},
    primaryClass={cs.LO cs.CC}
}