| Autor: |
Chen, Lijie, Li, Jiatu, Oliveira, Igor C. |
| Rok vydání: |
2024 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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$. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
