¿Quién introdujo la clase de complejidad AC?

Hoy enseñé los límites inferiores de , y uno de los estudiantes preguntó por la razón del nombre . La explicación oficial es que la "A" significa "Alternancia". $AC^0$ $AC$

Recuerdo vagamente que me dijeron hace muchos años que ~~Nick Pippenger~~ Steve Cook nombró a después de Nick Pippenger (clase de Nick), y más tarde Nick nombró a después de Steve (clase de Steve). $NC$ $SC$

La parte de la historia está documentada, por ejemplo, en Wikipedia y en el complejo zoológico, la historia de se cuenta aquí . $NC$ $SC$

Me pregunto si tiene una historia similar, pero no pude encontrar ninguna referencia al inventor de $AC$ $AC$

¿Alguien sabe quién definió ? $AC$

cc.complexity-theory reference-request ho.history-overview Dana Moshkovitz
fuente

Acabo de darme cuenta de la pregunta sobre "La clase de Steve" (después de Steven Cook) cstheory.stackexchange.com/questions/9298/… , y creo que tal vez fue la clase de la historia, y no AC.

Dana Moshkovitz

Furst, Saxe y Sipser no le dan un nombre a AC0, por lo que puedo decir. Pero una de sus principales aplicaciones es separar PSPACE de PH (= lenguajes computables mediante máquinas alternativas con un número constante de alternancias) en relación con un oráculo. Tal vez el aire acondicionado proviene de la aplicación alternativa de TM ..

Sasho Nikolov

Según Nick Pippenger (vea la pregunta vinculada por Dana en el comentario), los nombres SC y NC aparecieron en la Universidad de Toronto cuando Pippenger estaba visitando el grupo de Teoría, al que pertenece Steve Cook. Otro famoso teórico en Toronto es Allan Borodin. ¿Podría AC representar a la clase de Allan, para que no esté celoso? Podría estar divagando ...

Bruno

No hay historia detrás de esto. A significa alternancia.

Tayfun Pay

Creo que la notación AC aparece por primera vez en "Una taxonomía de problemas con algoritmos paralelos rápidos" de Cook de 1985. En la página 11 (página 12 de la revista) leemos:

Para establecer una forma más general de este resultado, presentamos la siguiente terminología.

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

Esta clase es en realidad una versión uniforme de AC.

Sigue una caracterización alternativa de Ruzzo y Tompa, que aparece en un informe técnico de Stockmeyer y Vishkin, y más tarde en "Reductibilidad de profundidad constante" por Chandra, Stockmeyer y Vishkin de 1984. Usan la notación TAMAÑO-PROFUNDIDAD (poli, constante) (ver página 3).

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

Todos estos documentos mencionan muchas máquinas Turing alternadas, dando crédito a la hipótesis de que A significa alternar.

Yuval Filmus
fuente

¿Quién introdujo la clase de complejidad AC?

Respuestas: