Kto wprowadził klasę złożoności AC?

Uczyłem dolne granice dzisiaj, a jeden z uczniów zapytał o powód nazwą C . Oficjalne wyjaśnienie jest takie, że „A” oznacza „Alternacja”.$AC^0$$AC$

Nie pamiętam, jak wiele lat temu powiedziano mi, że Nick Pippenger Steve Cook nazywa się $NC$ cześć Nicka Pippengera (klasa Nicka), a później Nick nazwał cześć Steve'a (klasa Steve'a).$SC$

część historii jest udokumentowane, na przykład, w Wikipedia i na złożoność zoo, historia dla $NC$ jesttutajopowiadana.$SC$

Zastanawiam się, czy C ma podobną historię, ale nie mogłem znaleźć żadnego odniesienia do$AC$ wynalazcy „s.$AC$

Czy ktoś wie, kto zdefiniował ?$AC$

Uważam, że notacja AC pojawia się po raz pierwszy w „Taksonomii problemów z szybkimi algorytmami równoległymi” Cooka z 1985 r. Na stronie 11 (strona 12 czasopisma) czytamy:

Aby podać bardziej ogólną formę tego wyniku, wprowadzamy następującą terminologię.

Definicja . , dla k = 1 , 2 , … , jest klasą problemów rozwiązanych przez bankomat w przestrzeni O ( log n ) i głębokości przemiennej O ( log k n $AC^k$$k=1,2,\ldots$$O(\log n)$$O(\log^k n)$ .

Ta klasa jest w rzeczywistości jednolitą wersją AC.

Następuje alternatywna charakterystyka Ruzzo i Tompy, pojawiająca się w raporcie technicznym Stockmeyera i Vishkina, a następnie w „Stałej redukcji głębokości” Chandry, Stockmeyera i Vishkina z 1984 r. Używają notacji SIZE-DEPTH (poli, stała) (patrz strona 3).

$AC^k \subseteq NC^{k+1}$

Wszystkie te artykuły wspominają wiele o naprzemiennych maszynach Turinga, co potwierdza hipotezę, że A oznacza przemienność.