Siapa yang memperkenalkan kelas kompleksitas AC?

Saya mengajar batas bawah saat ini, dan salah satu siswa ditanya tentang alasan nama A C . Penjelasan resmi adalah bahwa "A" adalah singkatan dari "Alternation".$AC^0$$AC$

Samar-samar saya ingat diberi tahu bertahun-tahun yang lalu bahwa Nick Pippenger Steve Cook menamai setelah Nick Pippenger (kelas Nick), dan kemudian Nick menamai S C setelah Steve (kelas Steve).$NC$$SC$

The bagian dari cerita didokumentasikan, misalnya, di Wikipedia dan di kebun binatang kompleksitas, cerita untuk S C diceritakan di sini .$NC$$SC$

Aku bertanya-tanya apakah memiliki sejarah yang sama, tapi aku tidak bisa menemukan referensi untuk A C penemu 's.$AC$$AC$

Apakah ada yang tahu siapa yang mendefinisikan ?$AC$

Saya percaya bahwa notasi AC pertama kali muncul dalam Cook "Taksonomi Masalah dengan Algoritma Paralel Cepat" dari tahun 1985. Pada halaman 11 (halaman 12 jurnal) kita membaca:

Untuk menyatakan bentuk yang lebih umum dari hasil ini, kami memperkenalkan terminologi berikut.

$AC^k$$k=1,2,\ldots$$O(\log n)$$O(\log^k n)$

Kelas ini sebenarnya adalah versi AC yang seragam.

Berikut mengikuti karakterisasi alternatif oleh Ruzzo dan Tompa, muncul dalam laporan teknis oleh Stockmeyer dan Vishkin, dan kemudian di "Konstan reducibilitas" oleh Chandra, Stockmeyer dan Vishkin dari 1984. Mereka menggunakan notasi SIZE-DEPTH (poli, konstan) (lihat halaman 3).

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

Semua makalah ini menyebutkan mesin Turing bergantian banyak, memberikan kepercayaan pada hipotesis bahwa A adalah singkatan dari berganti-ganti.