Arithmetic Circuits and Polynomial Replacement Systems.
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 $\numP$-complete.
Introduction
1.1 Motivation
g3
When and \Theta replace  and " in the adjacent figure, the gate g 1 on input
evaluates to 9. Equivalently, the tree-like Boolean circuit
T obtained from the circuit drawn has 9 proof trees [VT89], i.e. 9 different
minimal subcircuits witnessing that T outputs 1 (gates replicated to
form T are independent). This relationship between proof tree counting
and monotone arithmetic circuits was used by Venkateswaran [Ven92] to
characterize nondeterministic time classes, including #P [Val79], and by
Vinay [Vin91a] to characterize the counting version of LOGCFL [Sud78].
The same relationship triggered the investigation of #NC 1 by Caussinus et al. [CMTV98], and
that of #AC 0 by Allender et al. [AAD97]. See [AML98, L"eT98, All98] for recent results and for
motivation to study such "small" arithmetic classes.
A recent goal has been to capture small arithmetic classes by counting objects other than proof
trees, notably paths in graphs. Allender et al. [AAB succeeded in identifying appropriate
graphs for #AC 0 . Our early motivation for the present work was the desire to avoid unwinding
circuits into trees before counting their "proofs". Define a proof circuit to be a minimal subcircuit
witnessing that a circuit outputs 1. More precisely, for a Boolean circuit C and an input x, a proof
circuit is an edge-induced connected subcircuit of C which evaluates to 1 on x. This subcircuit
must contain the output gate of C, as well as exactly one C-edge into each -gate and all C-edges
Informatique et recherche op'erationnelle, Universit'e de Montr'eal, C.P. 6128, Succ. Centre-Ville, Montr'eal
(Qu'ebec), H3C 3J7 Canada. Research performed in part while on leave at the Universitat Tubingen. Supported by
the (German) DFG, the (Canadian) NSERC and the (Qu'ebec) FCAR. mckenzie@iro.umontreal.ca
y Theoretische Informatik, Universitat Wurzburg, Am Exerzierplatz 3, 97072 Wurzburg, Germany. Research
supported by Northern Telecom. vollmer@informatik.uni-wuerzburg.de
z Theoretische Informatik, Universitat Wurzburg, Am Exerzierplatz 3, 97072 Wurzburg, Germany. Research
supported by DFG, grant Wa 847/1-2. wagner@informatik.uni-wuerzburg.de
into each "-gate. The reader should convince herself that the circuit depicted above, which had 9
proof trees on input x proof circuits on that input.
What counting classes arise from counting proof circuits instead of trees? This question held
in stock several surprises, and led us down a totally unforeseen path. Our first surprise was the
following algorithm:
1. replace  by by \Theta in a negation-free Boolean circuit C,
2. view C as a straight-line program prescribing in the usual way a formal polynomial in the
input variables x
3. compute the polynomial top-down, with an important proviso: at each step, knock any
nontrivial exponent down to 1 in the intermediate sum-of-monomials representation.
We get the number of proof circuits of C on an input x by evaluating the final polynomial at x!
For example, the circuit depicted above had 7 proof circuits on input x
where
4 became g 4 in the middle of step 3.
One's intuition might be that such a simple strategy could be massaged into an arithmetic
circuit or at least into a sublinear parallel algorithm [VSBR83]. Our second surprise was that
counting proof circuits, even for depth-4 semi-unbounded circuits, is #P-complete. Hence, not
only is our strategy hard to parallelize, it likely genuinely requires exponential time!
Our "surprise" algorithm thus counts proof trees in the absence of the idempotent rules y y,
and it counts proof circuits in their presence. Moreover, whereas an arithmetic circuit computing
the number of proof trees of a circuit is readily available, producing such a circuit to compute proof
circuits seems intractable. What is special about the idempotent rules? What would the effect of
multivariate rules be? Which nontrivial rules would nonetheless permit expressing the counting in
the form of an arithmetic circuit? What is a general framework in which complexity questions such
as these can be investigated?
1.2 Results
We view our results as forming three main contributions.
Our first contribution is to define and classify polynomial replacement systems (prs for short).
Prs provide the answer to the framework question. A prs in its full generality is a start polynomial
together with a set of replacement rules. A replacement rule is a pair of polynomials
applicable to a polynomial q if q can be written in a form in
which appears. Applying (p then consists of replacing p 1 by p 2 (see Sect. 3 for formal
definitions).
A prs generally defines a set of polynomials, since the choice and sequencing of the rules, and the
way in which the rules are applied, may generate different polynomials. Computational problems
of interest include computing the polynomials themselves (poly), evaluating the polynomials at
specific points (eval), and testing membership in their ranges (range). We identify four natural
families of prs: simple if the rules only replace variables, deterministic if no two rules have the same
left-hand side, acyclic if no nontrivial infinite sequence of rules is applicable, and idempotent if the
rules (y 2 ; y) are present.
For general prs, we obtain canonical forms, we discuss representation, and we outline broad
complexity issues. Our detailed complexity analysis involves simple prs. For instance, we exhibit
simple and deterministic prs for which range is NP-complete. When the prs is given as part of
the input, poly is P-hard and in coRP, while range is NP-complete and eval is P-complete.
Our second contribution concerns the specific case of proof trees and proof circuits. We prove
that, to any Boolean circuit C and input x, corresponds an easily computable idempotent, simple,
deterministic and acyclic prs S having the property that the number of proof trees (resp. proof
circuits) of C on x is the maximum (resp. minimum) value of the eval problem for S on x,
and vice versa (see Lemma 5.13). This offers one viewpoint on the reason why our algorithm
from Subsect. 1.1 counts proof circuits correctly. We also prove that computing the minimum
of the eval problem for idempotent, simple, deterministic and acyclic prs is #P-complete, or
equivalently, that counting proof circuits is #P-complete under Turing reductions (but not under
many-one reductions unless P=NP). This provides a new characterization of #P which is to be
contrasted with Venkateswaran's (poly-degree,poly-depth) characterization [Ven92] and with the
retarded polynomials characterization of Babai and Fortnow [BF91]. We also prove that detecting
whether a circuit has more proof trees than proof circuits is NP-complete.
Our third contribution concerns the specific case of simple and acyclic prs. We prove that the
eval problem for such prs is the evaluation problem for f[; +; \Thetag-circuits. These circuits have
been considered previously (under the name hierarchical descriptions) in [Wag84, Wag86]. They
are obtained by generalizing, from trees to general circuits, the f[; +; \Thetag-expressions (a.k.a. integer
expressions), whose evaluation problem was shown NP-complete 25 years ago by Stockmeyer and
Meyer [SM73]. From a PSPACE-upper bound given in [Wag84] we conclude that evaluation of
simple acyclic prs has a polynomial space algorithm. Though this result could also have been
obtained more directly, we consider the link to f[; +; \Thetag-circuits very interesting. 1
1.3 Paper organization
Section 2 defines proof trees and circuits, and proves complexity results about them, in a self-contained
way independent from prs. The formal definition of a prs, as well as their canonical
forms, are found in Sect. 3. Section 4 briefly discusses the representation of polynomials and the
complexity of equivalence testing. Section 5 describes the four natural families of prs, and relates
these to straight-line programs, f[; +; \Thetag-circuits, and the proof trees vs. proof circuits problem
above. Section 6 investigates the complexity theoretic properties of simple prs in depth.
Counting Circuits vs. Counting Trees
2.1 Definition of Problems
By a circuit C, in this paper, we will mean a circuit over the basis f"; g in the usual sense, with
2n inputs labelled x
1 All the more interesting, following the clever proof by Ke Yang [Yan99], that evaluating f[; +; \Thetag-circuits is
PSPACE-hard. Ke's result implies that evaluating simple acyclic prs is PSPACE-complete, settling the question
which we posed at the 1999 DIMACS-DIMATIA workshop when describing the present work.
Fix an input x to C. Unwind C into a tree C 0 by (repeatedly) duplicating gates with fan-out
greater than 1. Define an accepting subtree as a subgraph H of C 0 whose gates evaluate to 1 and
which additionally fulfills the following properties: Subtree H must contain the output gate of C.
For every " gate v in H, all the input wires of v must be in H, and for every  gate v in H, exactly
one input wire of v must be in H. Only wires and nodes obtained in this way belong to H. By
#C(x) we denote the number of accepting subtrees of C.
Define an accepting subcircuit as a subcircuit H of C with the same properties as above. (I.e.,
the only difference is that now we do not start by unwinding C into a tree.) Given an input x, let
# c C(x) denote the number of accepting subcircuits of C on x.
Since an accepting subtree or subcircuit of a circuit C is some form of proof that C evaluates
to 1 on the given input, we will also refer to these as proof trees and proof circuits, resp. We will
consider the following problems:
Input: circuit C over f"; g, an input
number k in unary
Input: circuit C over f"; g, an input
Observe that if we unwind a circuit into a tree there may be an exponential blowup in size,
which has the consequence that the number of accepting subtrees may be doubly-exponential in the
size of the original circuit. This is not possible for the problem PC; the values of this function can
be at most exponential in the input length. In order to achieve a fair comparison of the complexity
of the problems, we therefore count proof trees only modulo an exponential number.
2.2 Some Initial Reductions
Lemma 2.1. PT is complete for FP under  log
.
Proof. By the well-known connection between counting accepting subtrees and the evaluation of
circuits [Vin91b, Ven92, Jia92], PT 2 FP since it is sufficient to evaluate such a circuit
modulo an exponential number.
Let now f 2 FP and x 2 f0; 1g   . Let f for inputs of length jxj be computed by the polynomial
size circuit C. Let m be the output gates of C, and let D those subcircuits
of C whose output gates are the gates . Say that C is unambiguous if for every circuit
D i there is at most one accepting subtree. We may suppose without loss of generality that C is
unambiguous [Lan93]. Now let C i be the trivial circuit with 2 i accepting subtrees. Then f(x) is
equal to the number of accepting subtrees of the circuit
Lemma 2.2. 1. The following problem is NP-complete under  log
Given a circuit C, is there
an input x such that #C(x) 6= # c C(x)?
2. The following problem is P-complete under  log
Given a circuit C and an input x 2 f0; 1g   ,
is
Proof. 1. Containment in NP is obtained by the following algorithm: On input C, guess an input
x and evaluate every gate in C. Check if there is an  gate g such that both its inputs evaluate
to 1, and there are at least 2 different paths from g to the output of C which are simultaneously
contained in some accepting subtree. This latter problem is essentially the GAP problem, since we
only have to check that there are two paths from g to C's output gate which join at some " gate
in C, such that all gates on these paths evaluate to 1.
To prove completeness, we give a reduction from 3-SAT: Given a 3-CNF formula F , we construct
an f"; g circuit C F with the same structure (that is, C F actually is a formula). Let C 0 be some fixed
circuit with differing numbers of accepting subtrees and subcircuits. Then the circuit
will have #C(x) 6= # c C(x) for some input x if and only if F is satisfiable.
2. Observe that the algorithm given in the proof of case 1 is deterministic, once the input x
is guessed. Hence the problem examined here is in P. Completeness is also shown along the lines
above, this time using the P-complete circuit value problem. q
Remark 2.3. If we restrict our attention to circuits of depth d, then the problem in case 2 of
the above lemma is in DSPACE(d); this is witnessed by the well-known depth-first search circuit
evaluation algorithm which is used to show
2.3 Counting Proof-Circuits is #P-Complete
For functions f; h, we say that f  log
1-T h if there are functions computable in logarithmic
space such that, for all x,
Theorem 2.4. PC is complete for #P under  log
1-T , but not under  p
Proof. For a conjunctive normal form H with 3 literals per clause, define SA(H) to be the number
of satisfying assignments to the variables of H. It is known (see [Val79]) that SA is  p
m-complete
for #P. We describe a  log
1-T -reduction from SA to PC.
be a conjunctive normal form with 3 literals per clause We define
a f; "g-circuit CH , all of whose inputs are set to 1, which has 6 levels, and is stratified, i. e., edges
are only between gates of adjacent levels. The levels are as follows:
1. Level 1 consists of the 1-gates v ikl for
2. Level 2 consists of the -gates v ik for incoming
edges from v ik0 and v ik1 .
3. Level 3 consists of the "-gates v i for incoming edges from
in .
4. Level 4 consists of the "-gates w
;. Gate w j has incoming edges from all
gates v i such that x j appears in the clause C i . Gate w 0
j has incoming edges from all gates v i
such that :x j appears in the clause C i . If by this construction a "-gate with no input wires
is produced, replace it by a constant 1-gate.
5. Level 5 consists of the -gates u Gate u j has incoming edges from the gates w j and
.
consists of the output gate which is a "-gate. It has incoming edges from the gates
Now let a 1g. We define the circuit CH (a 1 to be that subcircuit of CH
which results from cutting the edge between w and u j if a
n). The following facts are easy to see:
Fact 1: PC
Fact 2: (a exactly k clauses of H , PC
Fact 3: If (a
If (a does not satisfy H then PC
Fact 4: SA(H)
Hence SA(H) can easily be computed from PC(CH
1-T PC.
assume PC is complete for #P under  p
reductions. Let A 2 NP, then there is a function
#P such that x 2 A () f(x) ? 0 for all x. Under our assumption, there is a many-one
reduction g from f to PC, hence x 2 A () PC
latter condition however can
be checked in polynomial time since the underlying Boolean circuit has a positive number of proof
circuits if and only if it evaluates to 1 (over the Boolean semi-ring). q
The just given proof shows, that the problem PC remains #P-complete even restricted to
monotone circuits.
3 How to Generate Polynomials
A straight line program P over variables x is a set of instructions of one of the following
variable appears at most
once on the left hand side of the /. Those variables that never appear on the left hand side of
the / are the input variables. The variable xm is the output variable. Given values for the input
variables, the values of all other variables are computed in the obvious way. The value computed
by P is the value of the output variable. Let p P be the number-theoretic function computed in this
way by P .
A straight line program hence is just another way of looking at an arithmetic circuit. By the
above mentioned connection between the problem of counting proof trees and the evaluation of
arithmetic circuits, we see that an obvious algorithm to determine the number of proof trees of a
circuit consists of producing the appropriate straight line program and evaluating it in the order
of its variables.
In Sect. 1.1 we sketched a related proof circuit counting algorithm. Next we give a more precise
description of this algorithm: Given circuit C with input gates x inputs a
s be the non-input gates of C in topological order (i. e., a total order on the gates
of C which is consistent with the partial order given by the wires, hence there is a
wire from u to v).
1. Transform C into a straight-line program P as above.
2. In the following, we manipulate a polynomial p, which has variables g 1
Initially we set p to g s .
3. for do
3.1. Replace variable g i in p by the right hand side of that instruction in P , whose left hand
side is g i .
3.2. Transform p into the "sum-of-monomials" form.
3.3. Reduce all powers of variables in p to 1, i. e., replace all z 2 by z, where z is a variable.
At the end of this step, p will be a multilinear polynomial.
4. Substitute the values of a evaluate the resulting expression.
To see why this algorithm correctly counts proof circuits, let M(C) be the following nondeterministic
Turing machine. On input x, M(C) first evaluates all the gates of C on input x and prunes away
any zero gate. Unless the output gate g s of C was pruned away, M(C) starts at g s in the pruned
circuit and implements a recursive procedure evaluate. At an " gate g, evaluate triggers consecutive
recursive calls, one for each predecessor of g. At an  gate, evaluate triggers a single recursive call,
for a predecessor of g chosen nondeterministically. At a gate with no predecessor, evaluate simply
accepts. It is well known that M(C) has #C(x) accepting paths (see, e.g. [CMTV98]). But how can
M(C) be made to have # c C(x) accepting paths instead? Simply by making sure that, whenever
evaluate encounters a gate g a second time, g is treated as the constant gate 1: this will reflect the
fact that the choice of an accepting subcircuit rooted at g was already made, on the first encounter!
Let M c (C) be the machine M(C) modified in this way. The algorithm of Sect. 1.1, formalized
above, precisely computes the number of accepting paths of M c (C). Encountering a gate g twice
means that different paths out of g meet at an " gate (recall the proof of Lemma 2.2). This is
equivalent, in the straight-line arithmetic program point of view, to obtaining a monomial in which
appears. Replacing g 2 by g thus precisely models counting the number of accepting paths of
c (C), and thus the number of proof circuits of C on input x.
To summarize, the algorithm to compute proof circuits produces a polynomial (computing for
argument the number of proof trees of circuit C on input x 1 which is obtained
by evaluating the straight-line program given by C, but whenever possible during the computation
we replace a power x 2 by x. This is only a particular type of polynomial replacement systems
we define next. Polynomial replacement systems will produce sets of polynomials from a given
start polynomial, using rules replacing certain polynomials by other polynomials. This will be very
similar to the way formal grammars produce sets of words from a start symbol, applying production
rules.
In this paper we almost exclusively consider polynomials with nonnegative integer coefficients.
This is motivated by the application to proof trees and proof circuits discussed above. We write
to denote that p is such a polynomial in variables z
Below, the variable vector x will always be defined to consist of us say
that the variable x i is fictive (or, inessential) in the polynomial p(x) if for all a
we have p(a
This means that x i is
fictive in p if and only if p can be written as a term in which x i does not appear.
Definition 3.1. A polynomial replacement system (for short: prs) is defined as a quadruple
is the set of terminal variables,
is the set of nonterminal variables,
- q is a polynomial in the variables x the start polynomial, and
- R is a finite set of replacement rules, i. e., a finite set of pairs of polynomials in the variables
How does such a system generate polynomials?
Definition 3.2. Let
\Delta be a prs, let be polynomials in
the variables x.
there exist (p 3 and a polynomial p 5 (x; y) such that
Let
be the reflexive and transitive closure of =)

only if there exist t  0
and polynomials q 0
It turns out that the above form for derivations can be simplified:
Definition 3.3. Let be as above.
there exist (p 3
Let
be the reflexive and transitive closure of !
Lemma 3.4 (Normal Form of Replacement).
For any prs
\Delta and any polynomials p 1


Proof. Clearly,
We prove that p 1 =)

5 be a polynomial such that p 1
We can represent
Hence
. Defining the polynomials
moreover,
Consequently,

A prs thus generates a set of polynomials; hence we define:
Definition 3.5. For a prs
fi fi there exists p 0 (x) such that q
From the set poly(S) of polynomials we derive several sets of natural numbers, whose complexities
we will determine in the upcoming sections.
Definition 3.6. Let
\Delta be a prs. Define
\Phi p(a)
\Phi (a; p(a))
\Psi .
Observe that if we also allow negative numbers as coefficients for our polynomials, then there are
prs S such that range(S) is not decidable. This is seen as follows. By the Robinson-Matiasjevic
result (see [Mat93]), every recursively enumerable set can be represented in the form
\Phi p(a)
a 2 N n
\Psi where p is a suitable n-ary polynomial with integer coefficients. Now let p be such
an n-ary polynomial such that
\Phi p(a)
\Psi is not decidable. Defining the prs S
p(a)
\Psi .
Besides the membership problems poly(S), range(S), and eval(S), we also consider the
corresponding variable membership problems.
prs and p 2 poly(S)
prs and a 2 range(S)
\Psi .
4 Representations of Polynomials and Equivalence Test
When we want to examine the complexity of the above defined sets we have to talk about representations
of polynomials. We distinguish different kinds of representations.
Definition 4.1. Let p(x) be a polynomial.
(1) The full representation of p is its sum-of-monomials form. That is, we describe p as a sequence
of vectors (c; e each consisting of nonnegative integers, where c; e
are given in unary. Such a vector stands for the monomial c \Delta
(2) In the extended full representation (ef representation, for short), we describe p as a sequence
of vectors as above, but this time c is given in binary while all numbers e are given
in unary.
(3) In the formula representation, p is described by a formula involving the variables x. More
precisely, the set of formulas in variables x is defined inductively by the following rules:
(a) are formulas.
(b) If F; G are formulas, then so are
(4) In the straight-line program representation (slp representation, for short), we describe p by a
straight-line program with input variables x that computes p.
If \Phi is a representation of a polynomial of one of the above types, then we denote the polynomial
represented by \Phi by p \Phi .
It is easy to see that the above definition introduces a chain of representations with increasing
succinctness. For every representation of type (i) of a polynomial, equivalent representations of
types (j) for j ? i can be computed in logarithmic space. Moreover, if p has a full or ef or formula
representation of size n, then the degree of p is bounded by n, and if p has an slp representation of
size n, then the degree of p is at most exponential in n.
The idea to use slp's as a data structure for polynomials was introduced and promoted by
Erich Kaltofen (see, e.g., [Kal88]). Though the succinctness of this way of representing polynomials
compared with full or ef representation (or other so called sparse representations considered in the
literature) seems to be non-negligible, one of the results of this paper will be that the complexity of
the sets defined in Sect. 3 does not differ when we go from one form of representation to another.
A central problem in the upcoming sections will be the complexity of the problem to determine
if two representations stand for the same polynomial, i. e., the complexity of the equivalence problem
are representations of polynomials such that p \Phi 1
for the various types of representations. A similar result, as we give in our next theorem, was
obtained in [IM83].
Theorem 4.2. The equivalence problem is
1. in P for full and ef representation;
2. in coRP for formula and slp representation.
The proof will make instrumental use of the following well-known result [Sch80, Zip79] (see also
[MR95, p. 165f]):
Proposition 4.3 (Schwartz-Zippel). Let p(x a polynomial of degree d over some
field F, that is not the zero polynomial. Let S ' F be a finite set, and let a a n be chosen
independently and uniformly at random from S. Then
Proof. (of Theorem 4.2)
Two polynomials in (extended) full representation are equivalent if and only if they have the
same monomials. This can be checked in polynomial time.
Given now two formulas F 1 and F 2 , we know that the degree d of the two represented polynomials
is at most linear in the length of F 1 and F 2 . Hence by Proposition 4.3 it suffices to evaluate F 1 and
F 2 for a random input drawn from an exponential number of possible input vectors. The actual
evaluation of the formulas is in P.
Finally we are given two slp's P 1 and P 2 . Compared with the above, we now have to deal with
the fact the degree of the represented polynomial can be exponential, hence the numbers we operate
with can be double exponential in Therefore we cannot carry out the necessary
arithmetic operations in polynomial time. Instead we proceed as follows (see also [MR95, p. 169]):
Suppose the two numbers
are different, then ja \Gamma bj can have at most 2 n different prime
divisors. Let (m) denote the number of primes smaller than or equal to m. Hence for a random
prime smaller than k2 n log(k2 n ), the probability that a j b (mod p) is at most 2 n
O
. Thus if two numbers are different, then they are different modulo most small primes.
Hence are not equivalent iff for most inputs out of an exponential range we get
inequality iff for most inputs out of an exponential range we get inequivalence modulo most small
primes. Since the set of prime numbers is in ZPP, this algorithm is an RP algorithm. q
Different Types of Replacement Systems
The definition of polynomial replacement systems we presented above is very general. Here, we
introduce a number of natural restrictions. Our approach is similar to the way different restrictions
of grammar types were introduced, e.g., in the definition of the classes of the Chomsky hierarchy.
We will later view the problems of counting proof trees and proof circuits as two instances of a
problem about these restricted prs types.
5.1 Simple Polynomial Replacement Systems
Definition 5.1. A prs
\Delta is simple (or context-free), if the
polynomials in the left-hand sides of the rules of R are variables from fx g.
All definitions made in the preceding section for general prs carry over to the special cases of
simple systems. However, for simple prs we additionally define a particular type of replacement,
where the application of a rule (z; q) results in the replacement of all occurrences of z with q. This
latter form is denoted by j=)
, in contrast to the notation =)
for the derivations defined so far.
Definition 5.2. Let
\Delta be a simple prs.
there exist R such that
Let
be the reflexive and transitive closure of j=)
For the sets of polynomials and numbers derived from simple systems using our new derivation
type, we use the same names as before but now use square brackets instead of parentheses
Definition 5.3. For a simple prs
fi fi there exists p 0 (x) such that q
As in the case of poly(S) we define
Definition 5.4. Let
\Delta be a simple prs. Define
\Phi p(a)
(a; p(a))
We also define the following variable membership problems:
simple prs and p 2 poly[S]
simple prs and a 2 range[S]
fi fi S simple prs; p 2 poly[S] and a 2 N
\Psi .
It is clear that for any simple prs S, we have poly[S] ' poly(S); hence also range[S] '
range(S), eval[S] ' eval(S), poly[\Delta] ' poly(\Delta), range[\Delta] ' range(\Delta), and eval[\Delta] ' eval(\Delta).
5.2 Simple Deterministic or Acyclic Polynomial Replacement Systems
Definition 5.5. A prs
is said to be deterministic, if no
two different rules in R have the same left-hand side.
Definition 5.6. Let
be a prs. The dependency graph G S
of S is the directed graph G
consists of all edges (j; i) for which
there exists a rule (p R such that x i is essential in p 1 and x j is essential in p 2 . The prs S is
said to be acyclic, if its dependency graph G S is acyclic.
Lemma 5.7. For every simple and deterministic prs S, there exists a simple, deterministic, and
acyclic prs S 0 such that The system S 0 can be
obtained from S in polynomial time.
Proof. Let
\Delta be a simple and deterministic prs. If S is not
acyclic then there exist k  1, such that
is essential in p r for (where we set i
are nonterminal variables they have to be fictive in every polynomial p such
that q
poly(S). However, S is deterministic, and hence such a replacement
would necessarily run along the cycle described by the rules
if p has a non-fictive variable from fx
g then every p 0 such that p
have a non-
fictive variable from fx i 1
g. Thus we have
where
or an essential variable in p is from fx i 1
Now we repeat this cycle removement step as long as the prs still has cycles. Since in every step at
least one nonterminal variable is removed, we get after a polynomial number of steps a prs which
is simple, deterministic and acyclic. q
We also obtain the following easy properties:
Lemma 5.8. 1. If S is a simple and deterministic prs then poly[S], and this set
consists of at most one polynomial.
2. If S is a simple and acyclic prs then poly(S) and poly[S] are finite.
Proof. If S is simple, deterministic, and without loss of generality moreover acyclic, then the rules
replace every variable by a unique polynomial. Since S is simple we always have to replace all
occurrences of each nonterminal variable sooner or later. Hence the result of the whole derivation
process is unique.
If S is acyclic then every nonterminal variable can only be replaced in a constant number of
steps, hence we can only obtain finitely many polynomials. q
Note that there are simple and acyclic prs S such that poly[S] ( poly(S). For example take
4xg. Thus,
the requirement that S is deterministic is necessary in Lemma 5.8.1.
In the remainder of this subsection, we relate simple deterministic and simple acyclic prs to
different forms of circuits operating over the natural numbers.
First, it is intuitively clear that there is some connection between simple, deterministic, and
acyclic systems and straight-line programs. This is made precise in the following lemma.
Lemma 5.9. 1. If S is a simple, deterministic, and acyclic prs such that poly(S) 6= ; then
there exists a slp P such that g.
2. If P is a slp then there exists a simple, deterministic, and acyclic prs S such that fp P
poly(S).
3. The transformations from a simple, deterministic, and acyclic prs to the corresponding slp
and vice-versa can be computed in logarithmic space.
Proof. The program P is obtained from S by transforming every single replacement rule into
a sequence of slp instructions and then ordering these according to a topological order of G S .
Statement 2 is proved similarly. Statement 3 is obvious. q
Next we show that acyclic systems are strongly related to a new type of arithmetic circuit
we now define. These circuits are immediate generalizations of integer expressions, introduced by
Stockmeyer and Meyer [SM73]. Therefore we call our circuits integer circuits (not to be confused
with ordinary arithmetic circuits), or, referring to the operations allowed, ([; +; \Theta)-circuits.
An integer circuit with n inputs is a circuit C where the inner nodes compute one of the
operations [; +; \Theta. Such a circuit C has a specified output gate g s . It computes a function
We first define for every gate g 2 C the function f g computed by g.
1. If g is an input gate x i , then f g (a for all a
2. If g is + gate with predecessors g l ; g r , then f g (a
l
\Psi . The function computed by a \Theta gate is defined analogously.
3. If g is a [ gate with predecessors g l ; g r , then f g (a l
Finally, the function computed by C is f gs .
The following relation between simple, acyclic replacement systems and integer circuits is obtained
by an easy induction:
Lemma 5.10. 1. For every simple, acyclic prs
\Delta , there
is an integer circuit C with n inputs such that f C
\Psi for all a 2 N n .
2. For every integer circuit C with n inputs, there is a simple, acyclic prs S such that
(a) for all a 2 N n .
3. The transformations from a simple, acyclic prs to the corresponding integer circuit and vice-versa
can be computed in logarithmic space.
We consider the following problems:
\Phi (C; a
is an integer circuit with n inputs,
is an integer circuit with n inputs,
Analogous notations will be used when we restrict the gate types allowed.
The following lemma is immediate from Lemma 5.10:
Lemma 5.11. For all representations, the following holds:
1. N-MEMBER([;+; \Theta) j log
eval(\Delta).
2. N-RANGE([;+; \Theta) j log
range(\Delta).
5.3 Idempotent Polynomial Replacement Systems
Definition 5.12. For a prs
\Psi\Delta be the idempotent prs derived from S.
In the case that S is simple (deterministic, acyclic, resp.), we will say that S idem is an idempotent
simple (deterministic, acyclic, resp.) prs.
For a prs
\Delta and a 2 N n , we write mineval(S; a) as a
shorthand for min
p(a)
\Psi (analogously, we use maxeval(S; a)).
Lemma 5.13. 1. For every Boolean circuit C, input x, and k 2 N, there exists a simple, deterministic
and acyclic polynomial replacement system S such that mineval
# c C(x), and maxeval
2. For every simple, deterministic, and acyclic prs S idem there exists a Boolean circuit C such
that mineval
3. The transformations from an idempotent simple, deterministic, and acyclic prs to the corresponding
circuit and vice-versa can be computed in logarithmic space.
Proof. Arithmetic circuits and straight-line programs are only two different views of the same
concept. Hence we go from circuit C to system S and vice versa exactly as in Lemma 5.9. Clearly
the simple, deterministic, and acyclic system S computes #C(x) as explained in the discussion in
the beginning of Sect. 3.
Now convert S into the idempotent system S idem . That the number of proof circuits coincides
with the minimal element in eval
\Delta is a consequence of the algorithm given at the
beginning of Sect. 3. The minimal element is obtained if and only if during the derivation of a
polynomial, all rules
are applied whenever possible. The maximal element is obtained if
and only if we never pick such a rule, i. e., if we use only rules from S. q
6 Complexity Results for Simple Replacement Systems
6.1 Deterministic Systems
In this section, we consider the complexity of the above defined sets for simple replacement systems.
Let us start with the complexity of fixed membership problems.
Theorem 6.1. Let S be simple and deterministic.
1. poly(S); poly[S] are P-complete for all representations.
2. range(S); range[S] 2 NP. In fact, there are systems S such that the problems range(S)
and range[S] are NP-complete.
3.
Proof. First we recall that poly(S) and poly[S] consist of at most one polynomial p. In full and ef
representation, p has only finitely many representations, hence the complexity of poly(S); poly[S]
is trivial. However, in formula and slp representation, p may have infinitely many representations.
That is, we face the following problem: Given an slp P (the case of formulas is even easier), does
(where p is fixed)?
Say that P is reduced if the following holds: P has no instructions of the form x
the x j never appears on the right hand side of any other instructions (unless x j is the output
variable). Additionally, if x j / x is an instruction in P , then the polynomials computed
by x i and x k are both not the constant zero polynomial (otherwise, the instruction is useless, for,
e. g., if x hence we do not compute anything new; we might delete the above
instruction and in further instructions we use x k instead of x j ). Similarly, for x j
require that x i and x k are not constant one.
Now the following holds: Every polynomial p has only finitely many representations by reduced
slp's (except for an isomorphic renumbering of the variables). Moreover, a program P can be
transformed into reduced form as follows: Inductively, determine the sets of variables that compute
the constant zero or constant one polynomial. Then remove those instructions that do not compute
a new polynomial, and change the variables in the other instructions as described above. This shows
that poly(S); poly[S] 2 P.
Hardness follows from a reduction from the circuit value problem as follows: Let C be a Boolean
circuit. Let p be the polynomial that gives the number of proof trees of C. Let
does not evaluate to 1 iff C is not in CVP.
For 2 we have to decide the range of a multivariate polynomial with nonnegative coefficients.
This is clearly in NP by the obvious guessing algorithm. For the hardness proof, we give a reduction
from the quadratic Diophantine equations problem (problem AN8 in [GJ79, p. 250]) as follows: This
problem consists of all triples (a; b; c) such that the quadratic equation has a solution
in positive integers. Define hx;
Now, define the 4-variable polynomial p(u; v; x; vy. Then for all a; b; c 2 N, the
equation has a solution if and only if there are x; y such that p(a; b; x;
only if there are x; y such
ff
only if there are u; v; x; y such
that
Hence we see that the quadratic Diophantine equations problem
reduces to the range of the polynomial q(u; v; x;
ff .
For 3 observe we have to evaluate a fixed polynomial, hence the result follows since addition
and multiplication are in TC 0 . q
Concerning variable membership problems of simple, deterministic systems, we obtain:
Theorem 6.2. For simple and deterministic prs and for all representations,
1. poly(\Delta) and poly[\Delta] are in coRP and P-hard under  log
2. range(\Delta) and range[\Delta] are NP-complete under  log
3. eval(\Delta) and eval[\Delta] are P-complete under  log
.
Proof. Containment: In all cases, given the simple and deterministic prs S, first construct in
polynomial time the slp representation of the unique polynomial p (if any) in
by Lemma 5.7 and Lemma 5.8. Statement 1 then follows by equivalence test (Theorem 4.2). For
statement 2, guess suitable input values and evaluate p, for statement 3 just evaluate p (until
finished or the bounds are exceeded, as above).
Hardness: Statement 3: We give a reduction from the circuit value problem CVP as follows:
Given a circuit C and an input a to C, produce the replacement system S which computes the
number of proof trees of C on input a. S is simple and deterministic (see Sect. 3), and if we
"hardwire" the input a of C directly into S, the resulting polynomial has only fictive variables,
i. e., is essentially a natural number. Now C accepts a iff this number is greater than 0, hence
Proceeding as above, we obtain
(C; a) 2 CVP iff the constant 0 polynomial is not in poly(S) = poly[S]. Statement 2: Follows
from Theorem 6.1.2. q
6.2 Acyclic Systems
Let us next deal with simple, acyclic, but not necessarily deterministic systems. For such systems
S the sets poly(S) and poly[S] are finite (by Lemma 5.8), hence we obtain analogously to
Theorem 6.1:
Theorem 6.3. Let S be simple and acyclic.
1. poly(S); poly[S] 2 P for all representations.
2. range(S); range[S] 2 NP, and there are systems S such that the problems range(S) and
range[S] are NP-complete.
3.
Again, interesting questions arise when we examine variable membership problems.
Theorem 6.4. For simple and acyclic prs and for all representations,
1. poly[\Delta] is contained in MA and is NP-hard under  log
2. range[\Delta] and eval[\Delta] are NP-complete under  log
.
Proof. The containment proofs are similar to that of Theorem 6.2, but before applying Lemma 5.7
we select nondeterministically a deterministic prs by deleting some of the rules of the originally
given prs. The claim follows since
Hardness for poly[\Delta] is proven by giving a logspace many-one reduction from the sum-of-subset
problem SOS (problem SP13 in [GJ79, p. 223]) to poly[\Delta] as follows: Let m; b f0g.
Define the prs S by
\Phi
\Phi
Note that S is acyclic and simple, and poly[S] consists only of polynomials without essential
variables. For c 2 N, define p c Now we obtain
(b
Since a deterministic prs can (by Lemma 5.7) be assumed to be acyclic, hardness for range[\Delta]
follows as in Theorem 6.2.
We next prove hardness for eval[\Delta] by giving a logspace many-one reduction from the SOS
problem: Given m; b as in the proof of poly[\Delta] above. Then we obtain
(b a 2 N n . q
Next, we turn to different variable membership problems for simple, acyclic systems under
"=)"- derivations.
Stockmeyer and Meyer considered integer expressions (in our terminology, these are integer
circuits with fan-out of non-input gates at most 1) where the only operations allowed are [ and
+. They proved that the membership problem in that case is NP-complete. It is easy to see
that their result carries over to the case that we also allow multiplication, i. e., the problems
N-MEMBER([;+) and N-MEMBER([;+; \Theta) for expressions are NP-complete. The corresponding
problems for circuits were not considered in their paper, but in later papers by Wagner [Wag84,
Wag86] (under the name hierarchical descriptions). Only PSPACE as upper bound is known from
there.
Since (by Lemma 5.11), the member and range problems for these circuits are equivalent to the
eval(\Delta) and range(\Delta) problems for simple acyclic prs, we conclude: 2
Theorem 6.5. For simple and acyclic prs and for all representations,
1. poly(\Delta) 2 EXPTIME,
2. range(\Delta); eval(\Delta) 2 PSPACE.
6.3 Idempotent Systems
Again we note that also in this case poly(S) and poly[S] are finite, and we obtain results analogous
to Theorem 6.1:
Theorem 6.6. Let S be simple, deterministic, and acyclic.
1. poly(S idem
2 In the meantime we learned about a recent manuscript by Ke Yang, in which both circuit problems are shown
to be PSPACE-complete. From this we can conclude hardness in statement 2 of Theorem 6.5.
2. range(S idem In fact, there are systems S such that the problem range(S idem ) is
NP-complete.
3. eval(S idem
For the variable membership problems the following can be said:
Theorem 6.7. For idempotent, simple, deterministic, and acyclic prs and for all representations,
Proof. Follows by the trivial evaluation of the system. q
Lemma 5.13 shows the importance of the minimization and maximization operations in the case
of idempotent systems.
Theorem 6.8. For idempotent, simple, deterministic, and acyclic replacement systems and for all
representations,
1. the functions mineval(\Delta) and mineval[\Delta] are #P-complete under  log
1-T -reductions,
2. the functions maxeval(\Delta) and maxeval[\Delta] are FP-complete under  p
.
Proof. Immediate consequence of Lemma 2.1, Theorem 2.4 and Lemma 5.13. q
For completeness, we note:
Remark 6.9. For simple, deterministic and for simple, acyclic prs, the functions mineval(\Delta),
are FP-complete.
Proof. For simple, deterministic S and a 2 N   , obtain from Lemma 5.7 and Lemma 6.1 the slp-
representation of the unique polynomial p in poly(S) (if there is one). Then compute p(a) which
hence is the minimum and maximum. This element can be computed as in Theorem 6.2, showing
that the functions are in FP. Hardness follows immediately from Lemma 2.1.
For simple, acyclic S, we evaluate S according to a topological order of G S . The minimal
element is obtained if for every variable x we only consider those rules with left hand-side x, whose
right hand side is minimal. Hence we essentially deal with a deterministic system, and the upper
bound follows from the above. The case of maximization is treated similarly. Hardness follows
from hardness of the problem in the deterministic case. q
7 Conclusion
It might be of interest to consider the complexity of PC for circuits of restricted depth. The circuit
constructed in the proof of Theorem 2.4 has depth 5. Simply melting the " gates on levels 3 and 4
makes it depth 4. Furthermore, it is easy to see that for depth d+ 1 circuits with an  output-gate
the problem is as hard as for depth d circuits with an " output-gate. Next observe that the problem
is easy (i. e., in FP) for depth 2 circuits with an " output-gate (and hence also for depth 3 circuits
with an  output-gate).
This means that the complexity of PC is not known only in the case of depth 3 circuits with
an " output-gate (or, equivalently, for depth 4 circuits with an  output-gate). It is not hard to
see that this reduces to the case of 4-level stratified circuits with
level 1: 1-gates
level 2:  gates
level 3:  gates
- level 4: " gate (output gate)
This problem in its turn is equivalent to the following problem: Given: naturals b
the polynomial f(x
i=1;:::;m a ki \Delta x i with a ki 2 f0; 1g. Exploit distributivity
to reexpress this polynomial as a sum of monomials, and replace every x r
new polynomial. Goal: Compute
measured in the value - i. e. unary - of n
It is interesting to see that the problem of computing the permanent can be formulated in a
similar way, only substituting "replace every x r
"replace every x r
with 0". Nevertheless, it is not clear how to use this idea to reduce the problem of computing the
permanent to the above problem.
To determine the complexity of the sets range(S); range[S] for fixed S is in most of the cases
examined equivalent to determining the complexity of the range of a multivariate polynomial with
nonnegative integer coefficients. While this is always an NP-problem, we showed that there is a
4-variable polynomial of degree 6 whose range is NP complete. Can this be improved?
From a complexity theoretic point of view, further obvious open questions are of course, if the
gap between lower and upper bound in Theorems 6.5 and 6.7 can be closed.
A lot of interesting questions about prs remain open. To come back to some of the problems
posed in Subsect. 1.1, we did not look at all at multivariate rules. Also, it seems worthwhile to
examine if besides idempotent systems other prs families can related to various types of arithmetic
circuits and counting problems in Boolean circuits.

Acknowledgment

. We are grateful to Sven Kosub (Wurzburg) and Thomas Thierauf (Ulm) for
helpful discussions.



--R


On
Making computation count: arithmetic circuits in the nineties.

Arithmetization: a new method in structural complexity theory.
putation
Computers and Intractability
Modern Cryptography
Probabilistic algorithms for deciding equivalence of straight-line programs
Some questions concerning circuit counting classes and other low-level complexity classes
Greatest common divisors of polynomials given by straight-line programs
Unambiguity of circuits.

Randomized Algorithms.
Fast probabilistic algorithms for verification of polynomial identities.
Word problems requiring exponential time.
On the tape complexity of deterministic context-free languages
The complexity of enumeration and reliability problems.
Circuit definitions of non-deterministic complexity classes
Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits

Fast parallel computation of polynomials using few processors.
A new pebble game that characterizes parallel complexity classes.
The complexity of problems concerning graphs with regularities.
The complexity of combinatorial problems with succinct input repre- sentation
Magic circuit is PSPACE-complete
Probabilistic algorithms for sparse polynomials.
--TR
counting classes;arithmetic circuit;computational complexity