{"id":"arxiv/2602.09302","url":"https://arxiv.org/abs/2602.09302","tags":["cs.CC","cs.LO","math.LO"],"score":0,"title":"A Theory for Probabilistic Polynomial-Time Reasoning","domain":"cs.CC","source":"arxiv","authors":["Lijie Chen","Jiatu Li","Igor C. Oliveira","Ryan Williams"],"reviews":0,"subject":"cs.CC","summary":"In this work, we propose a new bounded arithmetic theory, denoted $APX_1$, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer science. Under plausible assumptions, $APX_1$ is strictly weaker than previously proposed frameworks, such as the theory $APC_1$ introduced in the seminal work of Jerabek (2007). From a computational standpoint, $APX_1$ is closely tied to approximate counting and to the central question in derandomization, the prBPP versus prP problem, whereas $APC_1$ is linked to the dual weak pigeonhole principle and to the existence…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-10","reactions":{}}