Click here to flash read.
arXiv:2404.11841v1 Announce Type: new
Abstract: 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$.
Click here to read this post out
ID: 812338; Unique Viewers: 0
Unique Voters: 0
Total Votes: 0
Votes:
Latest Change: April 19, 2024, 7:31 a.m.
Changes:
Dictionaries:
Words:
Spaces:
Views: 11
CC:
No creative common's license
No creative common's license
Comments: