Erkennung von Gruppen mit CC0 Schaltkreisen

Abstract

Seit Jahren gibt es ein Interesse den Zusammenhang zwischen Komplexitätsklassen von Schaltkreisen und abstrakten Algebren besser zu verstehen. Die ersten welche dieses Thema wirklich vorantrieben, waren Barrington und Thèrien mit Ihrer Arbeit über die Klasse NC¹ und endliche Monoide. Jedoch ist NC¹ nicht die einzige interessante Schaltkreisklasse. Wir wollen einen genaueren Blick auf die Unterklasse CC0 werfen und zeigen, dass sie dieselbe Aussagekraft wie auflösbare Gruppen haben. Wir werden zeigen, dass für jede auflösbare Gruppe ein Schaltkreis existiert unter Verwendung ihrer Normalreihe. Außerdem zeigen wir, dass für jeden CC0 Schaltkreis eine Gruppe existiert, welche wir aus zyklischen Gruppen mit Kranzprodukten erzeugen.

For years there has been an interest in the relation of the complexity classes of circuits and abstract algebras. The first to really promote this were Barrington and Thèrien with their paper about the class NC¹ and finite Monoids. However NC¹ is not the only interesting class of circuits. We want to take a look at the subclass CC0 and show that they have the same expressiveness as solvable groups. We will show that a circuit exists for every solvable group, using its subnormal series. Furthermore we show that we can create a group with wreath products of cyclic groups, for every CC0 circuit.