Qui a introduit la classe de complexité AC?

J'ai enseigné bornes inférieures aujourd'hui, et l'un des étudiants a demandé la raison du nom . L'explication officielle est que le "A" signifie "Alternance". $AC^0$ $AC$

Je me souviens vaguement, il y a de nombreuses années, que ~~Nick Pippenger~~ Steve Cook a nommé après Nick Pippenger (la classe de Nick), et plus tard Nick a nommé après Steve (la classe de Steve). $NC$ $SC$

La partie de l'histoire est documentée, par exemple, dans Wikipedia et dans le zoo de la complexité, l'histoire de est racontée ici . $NC$ $SC$

Je me demande si a une histoire similaire, mais je ne pouvais trouver aucune référence à l » inventeur. $AC$ $AC$

Est-ce que quelqu'un sait qui a défini ? $AC$

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

Je viens de remarquer la question sur "la classe de Steve" (après Steven Cook) cstheory.stackexchange.com/questions/9298/… , et je pense que c'était peut-être la classe de l'histoire, et non AC.

Dana Moshkovitz

Furst, Saxe et Sipser ne donnent pas de nom à AC0, pour autant que je sache. Mais l'une de leurs principales applications est de séparer PSPACE du PH (= langages calculables par machines alternées à nombre d'alternances constant) par rapport à un oracle. Peut-être que AC vient de l'application alternée des MT.

Sasho Nikolov

Selon Nick Pippenger (voir la question liée par Dana en commentaire), les noms SC et NC sont apparus à l'Université de Toronto lorsque Pippenger visitait le groupe Theory, auquel Steve Cook appartient. Un autre théoricien célèbre à Toronto est Allan Borodin. AC pourrait-il représenter la classe d'Allan, afin qu'il ne soit pas jaloux? Je pourrais être en train de divaguer ...

Bruno

Il n'y a aucune histoire derrière ça. A représente l'alternance.

Tayfun Pay

Je crois que la notation AC apparaît pour la première fois dans "A Taxonomy of Problems with Fast Parallel Algorithms" de Cook de 1985. À la page 11 (page 12 du journal), nous lisons:

Pour énoncer une forme plus générale de ce résultat, nous introduisons la terminologie suivante.

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

Cette classe est en fait une version uniforme d'AC.

Suit une caractérisation alternative par Ruzzo et Tompa, apparaissant dans un rapport technique de Stockmeyer et Vishkin, et plus tard dans "Constant depth reducibility" de Chandra, Stockmeyer et Vishkin de 1984. Ils utilisent la notation SIZE-DEPTH (poly, constante) (voir page 3).

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

Tous ces articles mentionnent beaucoup l'alternance des machines de Turing, donnant du crédit à l'hypothèse que A signifie l'alternance.

Yuval Filmus
la source

Qui a introduit la classe de complexité AC?

Réponses: