Wprowadzenie do złożoności obliczeniowej obwodów logicznych AC
W dziedzinie złożoności obliczeniowej obwodów logicznych, AC tworzy hierarchię klas złożoności. Każda klasa, oznaczona jako ACi, obejmuje języki, które są rozpoznawane przez obwody logiczne o głębokości
O(logi n) oraz posiadające wielomianową liczbę bramek o nieskończonym stopniu wejścia AND i OR.
Nazwa „AC” została wybrana w analogii do NC, przy czym litera „A” w skrócie oznacza „przemiennie” (alternating), co odnosi się zarówno do naprzemiennego używania bramek AND i OR w obwodach, jak i do naprzemiennych maszyn Turinga.
Najmniejszą klasą w tym kontekście jest klasa AC0, która składa się z obwodów logicznych o stałej głębokości oraz nieskończonym stopniu wejścia.
Cała hierarchia klas AC jest opisana jako:
AC = ⋃i ≥ 0 ACi
Relacja z NC
Klasy AC są ściśle powiązane z klasami NC, które są zdefiniowane w podobny sposób, ale z bramkami o stałym stopniu wejścia. Dla każdego i zachodzi:
NCi ⊆ ACi ⊆ NCi + 1
Bezpośrednią konsekwencją tego jest to, że NC = AC. W przypadku i = 0, wiemy, że włączenie jest ścisłe.
Wariacje
Możliwości klas AC mogą być zmieniane poprzez dodawanie dodatkowych bramek. Na przykład, jeśli wprowadzimy bramki, które wykonują obliczenia modulo dla pewnego m, otrzymujemy klasy ACCi[m].