Arithmetic Circuits and Polynomial Replacement Systems
Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner · SIAM Journal on Computing · 2004
This paper addresses the problems of counting proof-trees (as introduced by Venkateswaran and Tompa) and counting proof-circuits, a related but seemingly more natural question. These problems lead to a common generalization of straight-line programs which we call polynomial replacement systems {PRSs}. We contribute a classification of these systems and we investigate their complexity. Diverse problems falling within the scope of this study include, for example, counting proof-circuits and evaluating $\{\cup,+\}$-circuits over the natural numbers. A number of complexity results are obtained, including a proof that counting proof-circuits is $ umP$-complete.