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 $AP{X}_1$, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer scie…