AC

In der Komplexitätstheorie, speziell der , ist AC eine Komplexitätsklasse und ACi eine Hierarchie von Komplexitätsklassen. Für jedes enthält ACi die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe , polynomieller Größe, und Und- und Oder- mit unbeschränktem Fan-In und eventuell Nicht-Gattern an den Eingängen erkannt werden. Die Klasse AC ist dann definiert als Der Name AC wurde in Analogie zu NC gewählt, wobei A für „alternierend“ steht, was sich sowohl auf die Alternation zwischen Und- und Oder-Gattern in AC-Schaltkreisen als auch auf alternierende Turingmaschinen bezieht. Die kleinste AC-Klasse ist AC0, in der Sprachen liegen, die von Schaltkreisen konstanter Tiefe erkannt werden. Es gilt ; ansonsten ist unbekannt, ob die Hierarchie echt ist. Für jede natürliche Zahl p bezeichnet ACi[p] oder ACCi[p] die Klasse der Probleme, die von ACi-Schaltkreisen plus Modulo p-Gattern erkannt werden. Ein Modulo p-Gatter gibt dabei genau dann 1 aus, wenn die Zahl der Eingaben mit Wert 1 nicht durch p teilbar ist. Die Klassen i sind ähnlich definiert und erlauben beliebige Modulo-Gatter.