On the consistency of stronger lower bounds for NEXP

DOI10.46298/LMCS-21(4:23)2025MaRDI QIDQ6858429zbMATH OpenFDO

Authors Neil Thapen

Publication date 13 February 2026

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/LMCS-21(4:23)2025

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites work

• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Existence and feasibility in arithmetic
• Exponential lower bounds for the pigeonhole principle
• Feasibly constructive proofs of succinct weak circuit lower bounds
• scientific article; zbMATH DE number 3912375 (Why is no real title available?)
• scientific article; zbMATH DE number 1215494 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
• On the consistency of circuit lower bounds for non-deterministic time
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
• The provably total NP search problems of weak second order bounded arithmetic
• Unconditional Lower Bounds against Advice

This page was built for publication: On the consistency of stronger lower bounds for \(\mathsf{NEXP}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6858429)