Neil Thapen - On the consistency of stronger lower bounds for NEXP

lmcs:15468 - Logical Methods in Computer Science, November 21, 2025, Volume 21, Issue 4 - https://doi.org/10.46298/lmcs-21(4:23)2025
On the consistency of stronger lower bounds for NEXPArticle

Authors: Neil Thapen

It was recently shown by Atserias, Buss and Mueller 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.


Volume: Volume 21, Issue 4
Published on: November 21, 2025
Accepted on: October 12, 2025
Submitted on: April 7, 2025
Keywords: Logic in Computer Science, Computational Complexity, Logic

Consultation statistics

This page has been seen 562 times.
This article's PDF has been downloaded 245 times.