AC (complexity class)

from Wikipedia, the free encyclopedia

In complexity theory , specifically the circuit complexity , is AC a complexity class and AC i a hierarchy of classes complexity. For each contains AC i the formal languages that of circuit families with depth , polynomial size, and And- and Oder with unlimited fan-in and possibly non-gates are detected at the inputs. The class AC is then defined as

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

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

For each natural number p , AC i [p] or ACC i [p] denotes the class of problems recognized by AC i circuits plus modulo p gates. A modulo p gate outputs 1 if and only if the number of inputs with the value 1 is not divisible by p. The classes ACC i are defined similarly and allow any modulo gate.

Relation to other classes

The NC classes are defined similarly, but only allow circuit families whose gates have constant fan-ins. The TC classes extend the definition of AC with majority gates. For every i :

This means that NC = AC = TC = ACC.

literature

Web links

  • AC . In: Complexity Zoo. (English)