17
$\begingroup$

I taught $AC^0$ lower bounds today, and one of the students asked about the reason for the name $AC$. The official explanation is that the "A" stands for "Alternation".

I vaguely remember being told many years ago that Nick Pippenger Steve Cook named $NC$ after Nick Pippenger (Nick's class), and later Nick named $SC$ after Steve (Steve's class).

The $NC$ part of the story is documented, e.g., in Wikipedia and in the complexity zoo, the story for $SC$ is told here.

I wonder whether $AC$ has a similar history, but I couldn't find any reference to $AC$'s inventor.

Does someone know who defined $AC$?

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ I just noticed the question about "Steve's class" (after Steven Cook) cstheory.stackexchange.com/questions/9298/…, and I think that maybe this was the class from the story, and not AC. $\endgroup$
    – Dana Moshkovitz
    Sep 19, 2012 at 1:21
  • 2
    $\begingroup$ Furst, Saxe, and Sipser do not give AC0 a name, as far as I can tell. But one of their main applications is separating PSPACE from PH (=languages computable by alternating machines with constant number of alternations) relative to an oracle. Maybe AC comes from the alternating TMs application.. $\endgroup$
    – Sasho Nikolov
    Sep 19, 2012 at 2:21
  • 1
    $\begingroup$ According to Nick Pippenger (see the question linked by Dana in comment), the names SC and NC appeared at the University of Toronto when Pippenger was visiting the Theory group, to which Steve Cook belongs. Another famous theorist at Toronto is Allan Borodin. Could AC stand for Allan's class, so that he is not jealous? I might be rambling... $\endgroup$
    – Bruno
    Sep 19, 2012 at 15:45
  • $\begingroup$ There is no story behind it. A stands for alternation. $\endgroup$
    – Tayfun Pay
    Sep 20, 2012 at 23:04

1 Answer 1

Reset to default
18
$\begingroup$

I believe that the notation AC first appears in Cook's "A Taxonomy of Problems with Fast Parallel Algorithms" from 1985. On page 11 (page 12 of the journal) we read:

To state a more general form of this result we introduce the following terminology.

Definition. $AC^k$, for $k=1,2,\ldots$, is the class of problems solvable by an ATM in space $O(\log n)$ and alternation depth $O(\log^k n)$.

This class is actually a uniform version of AC.

There follows an alternative characterization by Ruzzo and Tompa, appearing in a technical report by Stockmeyer and Vishkin, and later on in "Constant depth reducibility" by Chandra, Stockmeyer and Vishkin from 1984. They use the notation SIZE-DEPTH(poly, constant) (see page 3).

Cook goes on to mention another unpublished characterization by himself and Ruzzo. Further results due to Ruzzo are mentioned, including $AC^k \subseteq NC^{k+1}$ ("On uniform circuit complexity", Ruzzo, 1981). The latter paper (as well as Ruzzo's earlier paper also mentioned) doesn't contain the notation AC, but rather a myriad of other notations, emphasizing the notion of uniformity used.

All these papers mention alternating Turing machines a lot, giving credence to the hypothesis that A stands for alternating.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.