TY  - THES
AB  - The circuit evaluation problem for various finitely generated algebraic structures is studied. More
precisely, for various rings, finite and infinite semirings, groups, and polynomial rings the complexity
of circuit evaluation is investigated. The focus is on parallel complexity classes like NC or
DET resp., the randomized parallel complexity class coRNC.
For the ring (Z,+,*) it is known that circuit evaluation is in the randomized complexity class
coRP. We show that under the assumption that the circuit has a constant bound for its multiplication
depth circuit evaluation for (Z,+,*) is complete for the class C=L. If instead, we assume
that the formal degree of the circuit is polynomially bounded, then circuit evaluation for (Z,+,*)
is complete for the class C=LogCFL.
For circuits over the polynomial ring (Z[x_1,...,x_k],+,*), where k is part of the input, circuit
evaluation is also known as polynomial identity testing and again the best known upper bound for
this problem is coRP. Under the assumption that the circuit is skew, it is known that the problem
is in coRNC. For skew circuits over (Z[x_1,...,x_k],+,*) with fixed k we show that circuit evaluation
is in C=L. The more general powerful skew circuits are introduced. These are skew circuits with
variables where input gates can be labeled by powers x^n for binary encoded numbers n. It is shown
that polynomial identity testing for powerful skew circuits belongs to coRNC2 which generalizes
the corresponding result for skew circuits. Two applications of this result are presented:
(i) Equivalence of higher-dimensional straight-line programs can be tested in coRNC2; this result
is even new in the one-dimensional case, where the straight-line programs produce strings.
(ii) The circuit evaluation problem for certain wreath products of finitely generated abelian groups
belongs to coRNC2.
For finitely generated linear groups, the best upper bound for circuit evaluation is again coRP,
which was shown by a reduction to polynomial identity testing. Conversely, circuit evaluation
for the linear group SL_3(Z) is equivalent to polynomial identity testing. In this work, it is shown
that circuit evaluation for every finitely generated nilpotent group is in DET. Within the
larger class of polycyclic groups we find examples where circuit evaluation is at least as hard as
polynomial identity testing for powerful skew circuits.
For finite semirings where semirings are not assumed to have an additive or multiplicative
identity, the following dichotomy is shown: if a finite semiring is such that (i) the multiplicative
semigroup is not solvable or (ii) it does contain a subsemiring with an additive identity 0 and a
multiplicative identity 1 not equal to 0, then the circuit evaluation problem for the semiring is P-complete.
In all other cases, the circuit evaluation problem is in DET.
An extension of the circuit evaluation problem to circuits over power sets is the circuit intersection
problem where circuits with additional union gates over the power set of a structure
are considered. We show that for a finite semiring S circuit intersection is in DET if S is a solvable
local group. Otherwise it is P-complete. It is known that circuit intersection for the ring
(Z,+,*) is NEXPTIME-complete. We use this to show that also for the linear group SL_5(Z) circuit
intersection is NEXPTIME-complete.
At the beginning of this thesis we show for the more classical word problem that this problem for
an infinite finitely generated linear group G is DLOGTIME-uniform TC0-complete if G is solvable
and that it is in DLOGTIME-uniform NC1 if G is virtually solvable.
AU  - König, Daniel
DA  - 2017
KW  - Komplexitätstheorie
KW  - Algorithmische Algebra
KW  - Combinatorial group theory
KW  - Parallel algorithms
LA  - eng
PY  - 2017
TI  - Parallel evaluation of algebraic circuits
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:467-11937
Y2  - 2024-11-22T00:33:05
ER  -