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 131 times.
    This article's PDF has been downloaded 66 times.