Go to page

Bibliographic Metadata

Restriction-Information
 The document is publicly available on the WWW.
Links
Abstract
( AEnglishA )

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.

Abstract
( AGermanA )

Das Auswertungsproblem für algebraische Schaltkreise für verschiedene endlich erzeugte algebraische

Strukturen wird bezüglich seiner Komplexität untersucht. Genauer gesagt wird dieses Problem

für verschiedene Ringe, endliche und unendliche Semiringe, Gruppen und Polynomringe betrachtet.

Hierbei liegt der Fokus auf parallelen Komplexitätsklassen wie NC oder DET sowie auf der

Komplexitätsklasse der Komplemente der randomisiert effizient parallelisierbaren Probleme coRNC.

Bekanntermaßen liegt das Auswertungsproblem für Schaltkreise über dem Ring (Z,+,*) in der

Komplextitätsklasse coRP, also der Klasse der Komplemente der in randomisierter Polynomialzeit

lösbaren Probleme. Es wird gezeigt, dass unter der Annahme, dass die multiplikative Tiefe des

Schaltkreises durch eine Konstante beschränkt ist, das Auswerten von Schaltkreisen vollständig für

die Klasse C=L ist. Nimmt man hingegen an, dass der formale Grad des Schaltkreises über (Z,+,*)

polynomiell beschr änkt ist, so erhält man Vollständigkeit für die Klasse C=LogCFL.

Für Schaltkreise über dem Polynomring (Z[x_1,..., x_k],+,*), wobei das k Teil der Eingabe ist,

liegt das Schaltkreisauswertungsproblem ebenfalls in der Klasse coRP. Unter der Annahme, dass für

jedes Multiplikationsgatter eines der beiden Eingangsgatter ein Eingangsgatter des gesamten Schaltkreises

ist (sog. schiefe Schaltkreise), weiß man, dass das Problem in der Klasse coRNC liegt. Es wird

gezeigt, dass mit der zusätzlichen Annahme, dass k konstant ist, das Auswerten von Schaltkeisen

in C=L liegt. Etwas mehr Ausdruckskraft besitzt eine neu eingeführte Klasse von Schaltkreisen, bei

der wir voraussetzen, dass eines der beiden Eingangsgatter eines multiplikativen Gatters von der

Form x^n ist und n als binär kodierte Zahl gegeben ist. Wir bezeichnen diese Schaltkreise als kraftvoll

schief. Für diesen Fall wird gezeigt, dass das Schaltkreisauswertungsproblem ebenfalls in coRNC

liegt. Dieses Ergebnis wird genutzt, um zwei Anwendungen zu zeigen: Einerseits wird gezeigt, dass

das Äquivalenzproblem für mehrdimensionale Straight-line programs in coRNC lösbar ist, was selbst

für den eindimensionalen Fall ein neues Ergebnis liefert. Außerdem zeigen wir, dass das Auswertungsproblem

für Schaltkreise über bestimmten Kranzprodukten von endlich erzeugten abelschen Gruppen ebenfalls in coRNC liegt.

Für endlich erzeugte lineare Gruppen liegt die beste bisher bekannte obere Schranke für das

Auswertungsproblem von Schaltkreisen erneut bei coRP, was mit Hilfe einer Reduktion auf das

Auswerten von Schaltkreisen über (Z,+,*) gezeigt wurde. Auf der anderen Seite konnte gezeigt

werden, dass das Schaltkreisauswertungsproblem für die lineare Gruppe SL_3(Z) und für (Z,+,*)

äquivalent zueinander sind. In dieser Arbeit wird gezeigt, dass das Auswerten von Schaltkreisen

für endlich erzeugte nilpotente Gruppen in DET liegt. Weiterhin wird gezeigt, dass es in

der größeren Klasse der polyzyklischen Gruppen eine Gruppe gibt, deren Auswertungsproblem für

Schaltkreise mindestens so schwer ist wie für kraftvoll schiefe Schaltkreise über (Z[x_1,...,x_k],+,*).

Für endliche Semiringe, wobei in einem Semiring weder ein multiplikativ noch ein additiv neutrales

Element verlangt wird, wird die folgende Zweiteilung gezeigt: Besitzt der Semiring ein multiplikativ

neutrales und ein von diesem verschiedenes additiv neutrales Element oder ist die multiplikative

Halbgruppe des Semirings nicht auflösbar, so ist das Schaltkreisauswertungsproblem vollständig für

die Klasse P. In allen anderen Fällen liegt es in der Klasse DET.

Eine Erweiterung des Auswertungsproblems für Schaltkreise ist das Schnittproblem für Schaltkreise.

Dieses agiert auf den Potenzmengen von algebraischen Strukturen und fragt für Schaltkreise

über diesen zusammen mit Vereinigungsgattern, ob der Durchschnitt zweier durch Schaltkreise repräsentierter Mengen leer ist. Es wird gezeigt, dass dieses Problem für eine endliche Halbgruppe in DET liegt, wenn es sich um eine lokale Gruppe handelt. Ansonsten ist das Problem vollständig für P.

Zusätzlich wird gezeigt, dass dieses Problem für die lineare Gruppe SL_5(Z) NEXPTIME-volständig

ist.

Zu Beginn dieser Arbeit wird das klassische Wortproblem für endlich erzeugte Gruppen betrachtet.

Es wird gezeigt, dass für eine endlich erzeugte lineare Gruppe das Wortproblem vollständig für

DLOGTIME-uniforme TC0-Schaltkreise ist, falls die Gruppe auflösbar ist. Ist sie hingegen virtuell auflösbar, so liegt das Wortproblem in DLOGTIME-uniformem NC1.

Stats