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.