2 papers
cs.CC2026
A Theory for Probabilistic Polynomial-Time Reasoning
Lijie Chen, Jiatu Li, Igor C. Oliveira +1
In this work, we propose a new bounded arithmetic theory, denoted , designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer scie…
cs.LO2025
On the Unprovability of Circuit Size Bounds in Intuitionistic
Lijie Chen, Jiatu Li, Igor C. Oliveira
We show that there is a constant such that Buss's intuitionistic theory does not prove that SAT requires co-nondeterministic circuits of size at least .…