3 papers
cs.LO2026
Quantified propositional calculi and narrow implicit proofs
Pavel Pudlák, Neil Thapen
In the implicit version of a propositional proof system Q, we work with Q-proofs that are not written down directly, but are succinctly encoded by circuits. Thus implicit Q-proofs…
cs.LO2025
On the consistency of stronger lower bounds for NEXP
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 arithmet…
cs.CC2025
How to fit large complexity classes into TFNP
Neil Thapen
Subclasses of TFNP (total functional NP) are usually defined by specifying a complete problem, which is necessarily in TFNP, and including all problems many-one reducible to it. We…