Wer hat die Komplexitätsklasse AC eingeführt?

Ich habe heute Untergrenzen unterrichtet , und einer der Schüler fragte nach dem Grund für den Namen . Die offizielle Erklärung ist, dass das "A" für "Alternation" steht. $AC^0$ $AC$

Ich kann mich vage daran erinnern, dass ich vor vielen Jahren ~~erfahren~~ habe, dass ~~Nick Pippenger~~ Steve Cook nach Nick Pippenger (Nicks Klasse) und später Nick nach Steve (Steves Klasse) benannt hat. $NC$ $SC$

Der - Teil der Geschichte ist dokumentiert, zum Beispiel in Wikipedia und in der Komplexität Zoo, die Geschichte für erzählte hier . $NC$ $SC$

Ich frage mich, ob eine ähnliche Geschichte hat, aber ich konnte keinen Hinweis auf den Erfinder von finden . $AC$ $AC$

Weiß jemand, wer definiert hat ? $AC$

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

Mir ist gerade die Frage nach "Steve's class" (nach Steven Cook) aufgefallen. Cstheory.stackexchange.com/questions/9298/… und ich denke, dass dies vielleicht die Klasse aus der Geschichte war und nicht AC.

Dana Moshkovitz

Fürst, Saxe und Sipser geben AC0 keinen Namen, soweit ich das beurteilen kann. Eine ihrer Hauptanwendungen ist jedoch die Trennung von PSPACE von PH (= Sprachen, die von wechselnden Maschinen mit konstanter Anzahl von Wechseln berechenbar sind) in Bezug auf ein Orakel. Vielleicht kommt AC aus der alternierenden TMs-Anwendung ..

Sasho Nikolov

Laut Nick Pippenger (siehe die Frage von Dana im Kommentar) tauchten die Namen SC und NC an der Universität von Toronto auf, als Pippenger die Theory-Gruppe besuchte, zu der Steve Cook gehört. Ein weiterer berühmter Theoretiker in Toronto ist Allan Borodin. Könnte AC für Allans Klasse stehen, damit er nicht eifersüchtig ist? Ich könnte streifen ...

Bruno

Es steckt keine Geschichte dahinter. A steht für Abwechslung.

Tayfun Pay

Antworten:

Ich glaube, dass die Notation AC erstmals 1985 in Cooks "Eine Taxonomie der Probleme mit schnellen parallelen Algorithmen" auftaucht. Auf Seite 11 (Seite 12 der Zeitschrift) lesen wir:

Um eine allgemeinere Form dieses Ergebnisses anzugeben, führen wir die folgende Terminologie ein.

Definition . für , ist die Klasse von Problemen, die von einem Geldautomaten im Raum und in der Wechseltiefe lösbar sind . $AC^k$ $k=1,2,\ldots$ $O(\log n)$ $O(\log^k n)$

Diese Klasse ist eigentlich eine einheitliche Version von AC.

Es folgt eine alternative Charakterisierung von Ruzzo und Tompa, die in einem technischen Bericht von Stockmeyer und Vishkin und später in "Constant Depth Reducibility" von Chandra, Stockmeyer und Vishkin aus dem Jahr 1984 auftaucht. Sie verwenden die Notation SIZE-DEPTH (poly, constant) (siehe Seite 3).

Cook erwähnt eine weitere unveröffentlichte Charakterisierung von ihm und Ruzzo. Weitere Ergebnisse aufgrund von Ruzzo werden erwähnt, einschließlich ("On Uniform Circuit Complexity", Ruzzo, 1981). Letzteres Papier (wie auch Ruzzos zuvor erwähntes Papier) enthält nicht die Notation AC, sondern eine Vielzahl anderer Notationen, wobei der Begriff der Einheitlichkeit betont wird. $AC^k \subseteq NC^{k+1}$

Alle diese Artikel erwähnen häufig alternierende Turing-Maschinen, was die Hypothese bestätigt, dass A für alternierend steht.

Yuval Filmus
quelle