Quem introduziu a classe de complexidade AC?

Hoje ensinei limites inferiores a e um dos alunos perguntou sobre o motivo do nome . A explicação oficial é que o "A" significa "Alternação". $AC^0$ $AC$

Lembro-me vagamente de ter sido informado há muitos anos que ~~Nick Pippenger~~ Steve Cook nomeou homenagem a Nick Pippenger (classe de Nick), e mais tarde Nick nomeou homenagem a Steve (classe de Steve). $NC$ $SC$

A parte da história está documentada, por exemplo, na Wikipedia e no zoológico de complexidade, a história da é contada aqui . $NC$ $SC$

Gostaria de saber se a tem uma história semelhante, mas não encontrei nenhuma referência ao inventor da . $AC$ $AC$

Alguém sabe quem definiu ? $AC$

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

Acabei de notar a pergunta sobre a "aula de Steve" (depois de Steven Cook) cstheory.stackexchange.com/questions/9298/… , e acho que talvez essa tenha sido a aula da história, e não AC.

Dana Moshkovitz 19/09/12

Furst, Saxe e Sipser não dão um nome ao AC0, pelo que sei. Mas uma de suas principais aplicações é separar PSPACE de PH (= linguagens computáveis por máquinas alternadas com número constante de alternâncias) em relação a um oráculo. Talvez AC vem do aplicativo TMs alternadas ..

Sasho Nikolov

Segundo Nick Pippenger (veja a pergunta vinculada por Dana no comentário), os nomes SC e NC apareceram na Universidade de Toronto quando Pippenger estava visitando o grupo Theory, ao qual Steve Cook pertence. Outro famoso teórico de Toronto é Allan Borodin. AC poderia representar a classe de Allan, para que ele não estivesse com ciúmes? Eu poderia estar divagando ...

de Bruno

Não há história por trás disso. A significa alternância.

Tayfun Pay

Acredito que a notação AC aparece pela primeira vez em "Uma taxonomia de problemas com algoritmos paralelos rápidos" de 1985. Na página 11 (página 12 da revista), lemos:

Para declarar uma forma mais geral desse resultado, introduzimos a seguinte terminologia.

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

Esta classe é na verdade uma versão uniforme do AC.

Segue uma caracterização alternativa por Ruzzo e Tompa, aparecendo em um relatório técnico de Stockmeyer e Vishkin, e mais tarde em "Redutibilidade de profundidade constante" por Chandra, Stockmeyer e Vishkin de 1984. Eles usam a notação SIZE-DEPTH (poly, constant) (veja a página 3).

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

Todos esses trabalhos mencionam muito as máquinas de Turing alternadas, dando credibilidade à hipótese de que A significa alternância.

Yuval Filmus
fonte

Quem introduziu a classe de complexidade AC?

Respostas: