AC (klasa złożoności)

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ą $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

${\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

${\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].