AC (complexity)

In complexity theory, specifically the circuit complexity, AC is a complex class and ACI a hierarchy of Komplexitäsklassen. For each ACi contains the formal languages ​​of logic families with depth, polynomial size, and And and Or are recognized with unbounded fan-in and possibly non- gates at the entrances. Class AC is then defined as

The name AC was chosen in analogy to NC, where A stands for " alternating ", which refers both to the alternation between And and Or gates in AC circuits as well as on alternating Turing machines.

The smallest AC class is AC0, are the languages ​​that are recognized by circuits of constant depth. It is true; otherwise it is unknown whether the hierarchy is real.

For every natural number p ACi [ p] or ACCI [ p ] denotes the class of problems that are recognized by ACi circuits plus modulo p gates. A modulo p gates are doing exactly then 1 if the number of entries with value 1 is not divisible by p. The classes are defined similarly, AccI allow arbitrary modulo gates.

Relation to other classes

The NC classes are defined similarly, but only allow circuit families whose gates have constant fan-in. The TC- classes extend the definition of AC by Majority gate. For each i, the following applies:

It follows NC = AC = TC = ACC.