We develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle ( dWPHP(PV) ), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM ) in PV 1 + dWPHP(PV) .
No takes yet. Share an insight, caveat, or question.
Emil Jeřábek (2007) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: