W złożoności obliczeniowej obwodów logicznych AC jest hierarchią klas złożoności. Każda klasa, ACⁱ, składa się z języków rozpoznawanych przez obwody logiczne z głębokością ${\displaystyle O(\log ^{i}n)}$ oraz wielomianową liczbę bramek o nieskończonym stopniu wejścia AND i OR.

Nazwę „AC” wybrano analogicznie do NC, przy czym „A” w nazwie oznacza „przemiennie” (alternating) i odnosi się zarówno do naprzemienności bramek AND i OR w obwodach, jak i do naprzemiennych maszyn Turinga.

Najmniejszą klasą prądu przemiennego jest prąd zmienny <sup id="mwFg">0</sup>, składający się z obwodów logicznych o stałej głębokości i nieskończonym stopniu wejścia.

Całkowita hierarchia klas AC jest zdefiniowana jako

${\displaystyle {\mbox{AC}}=\bigcup _{i\geq 0}{\mbox{AC}}^{i}}$

Związek z NC

Klasy AC są powiązane z klasami NC, które są zdefiniowane podobnie, ale z bramkami mającymi tylko stały stopień wejścia. Dla każdego i mamy

${\displaystyle {\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{NC}}^{i+1}}$

Bezpośrednią konsekwencją tego jest to, że NC = AC.

Wiadomo, że włączenie jest ścisłe dla i = 0.

Wariacje

Moc klas AC można wpłynąć poprzez dodanie dodatkowych bramek. Jeśli dodamy bramki, które obliczają działanie modulo dla jakiegoś m, mamy klasy ACCⁱ[m].

Przypisy