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

Uczyłem dolne granice dzisiaj, a jeden z uczniów zapytał o powód nazwą . 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 ma podobną historię, ale nie mogłem znaleźć żadnego odniesienia do $AC$ wynalazcy „s. $AC$

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

cc.complexity-theory reference-request ho.history-overview

— Dana Moshkovitz
źródło

Właśnie zauważyłem pytanie dotyczące „klasy Steve'a” (za Stevenem Cookiem) cstheory.stackexchange.com/questions/9298 /... i myślę, że może to była klasa z tej historii, a nie AC.

— Dana Moshkovitz,

O ile wiem, Furst, Saxe i Sipser nie nadają AC0 nazwy. Ale jednym z ich głównych zastosowań jest oddzielanie PSPACE od PH (= języki obliczalne przez naprzemienne maszyny o stałej liczbie zmian) względem wyroczni. Może AC pochodzi z naprzemiennej aplikacji TM.

— Sasho Nikolov,

Według Nicka Pippengera (patrz pytanie powiązane przez Dana w komentarzu), nazwy SC i NC pojawiły się na Uniwersytecie w Toronto, gdy Pippenger odwiedził grupę teorii, do której należy Steve Cook. Innym znanym teoretykiem z Toronto jest Allan Borodin. Czy AC może reprezentować klasę Allana, aby nie był zazdrosny? Mogę się włóczyć ...

— Bruno,

Nie kryje się za tym żadna historia. A oznacza przemianę.

— Tayfun Pay

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 , jest klasą problemów rozwiązanych przez bankomat w przestrzeni i głębokości przemiennej $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ść.

— Yuval Filmus
źródło