W teorii złożoności , AC 0 jest klasa złożoności zdefiniowane przez obwody logiczne o stałej głębokości. Jest częścią hierarchii AC . Klasa AC 0 zawiera dodawanie, ale nie zawiera funkcji parzystości, mnożenia lub predykatu pierwszości (patrz poniżej).
Klasa AC 0 jest klasa złożoności z problemami określana przez logicznych układów o stałej głębokości, wielomianu wielkości bramy są AND i OR , stopnie przychodzące nieograniczona (w rzeczywistości inne drzwi mogą być dopuszczone jak „ exclusive OR ” lub NIE bramy , ponieważ są one wyrażalne, bez zmiany złożoności, przez AND i OR ). Akronim AC pochodzi z obwodu naprzemiennego . Jest częścią hierarchii AC .
Dodatek jest w AC 0 . Dokładniej, dla wszystkich i, problem decyzyjny, który przyjmuje jako dane wejściowe 2n bitów, które reprezentują dwie liczby aib z n bitów i który oblicza i- ty bit sumy aib, jest w AC 0 .
Szczegóły obwodu o wielkości wielomianu i stałej głębokości do dodawaniaOto sposób na zbudowanie obwodu do obliczenia i- tego bitu sumy n-1 ... a 0 i b n-1 ... b 0 . Zwróć uwagę na logikę ∧ „i”, ∨ logiczną „lub” i ⊕ wyłączną lub. Uważamy j za zdanie, prawdziwe, jeśli j- ty bit a jest równy 1, a fałszywe w przeciwnym razie. Podobnie b j jako zdanie, prawda, jeśli j- ty bit b jest równy 1, a fałsz w przeciwnym razie. Podobnie oznaczamy s j jako zdanie, prawdziwe, jeśli j- ty bit s wynosi 1, a fałszywe w przeciwnym razie. Przedstawiamy również inne propozycje:
Mamy :
Liczba bramek w obwodzie odpowiadająca powyższym wzorom jest wielomianem w n. Ponadto głębokość obwodu jest stała, jak pokazano w obwodzie pokazanym na powyższej ilustracji.
Podobnie odejmowanie jest w AC 0 .
Funkcja parzystości jest predykatem, który zwraca 1, jeśli na wejściu liczba bitów 1 jest parzysta, a w przeciwnym wypadku zwraca 0. W latach 70. , nie było wiadomo, czy istnieją obwody AC 0 dla problemu kliki lub problemu komiwojażera . W rzeczywistości Furst, Saxe i Sipser oraz niezależnie Miklós Ajtai pokazali, że tak nie jest. Wykazali nawet, że znacznie prostszy predykat, a mianowicie funkcja parzystości , nie należy do AC 0 . Johan Håstad pokazał wtedy mocniejszy wynik, lemat zamiany (w) . Ponieważ funkcja parzystości jest w NC 1 , wnioskujemy, że włączenie AC 0 do NC 1 jest ścisłe.
Funkcja większości pobiera n bitów jako dane wejściowe i zwraca 1, jeśli ściśle więcej niż połowa bitów jest równa 1. Ta funkcja nie jest w AC 0 . Możemy to wykazać absurdalnie, jeśli większość jest w AC 0 , dodając dodatkowe bity, możemy sprawdzić, czy x ≥ k , gdzie x jest liczbą całkowitą reprezentowaną przez dane bity, a k jest stałą; stamtąd możemy sprawdzić, czy x = k ; i dlatego przetestuj parzystość , będąc w AC 0 , co jest sprzecznością.
Mnożenie nie znajduje się w AC 0 i jest pokazane przez zmniejszenie z funkcji parzystości. Z drugiej strony jest w NC 1 .
Predykat pierwszości, który sprawdza, czy liczba całkowita jest liczbą pierwszą, nie znajduje się w AC 0 .
Klasa AC 0 jest związana z logiką pierwszego rzędu w złożoności opisowej .