[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