Arithmetic Circuits and Polynomial Replacement Systems

Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


Abstract: 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. We contribute a classification of these systems and we investigate their complexity. Diverse problems falling in the scope of this study include, for example, counting proof circuits, and evaluating $\{\cup,+\}$-circuits over the natural numbers. The former is shown $\#P$-complete, the latter to be equivalent to a particular problem for replacement systems.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:22
Start Conference Manager
Conference Systems