[Proof Complexity] New preprint

thapen thapen at math.cas.cz
Mon Apr 7 10:54:08 CEST 2025


Dear colleagues,

I have posted a proof-complexity preprint on arxiv, "On the consistency 
of stronger lower bounds for NEXP", https://arxiv.org/abs/2504.03320

Abstract: It was recently shown by Atserias, Buss and Müller that the 
standard complexity-theoretic conjecture NEXP not in P / poly is 
consistent with the relatively strong bounded arithmetic theory V^0_2, 
which can prove a substantial part of complexity theory. We observe that 
their approach can be extended to show that the stronger conjectures 
NEXP not in EXP / poly and NEXP not in coNEXP are consistent with a 
stronger theory, which includes every true universal number-sort 
sentence.

Best wishes,

Neil Thapen


More information about the Proof-Complexity mailing list