<p>I believe that the <em>notation</em> 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:</p>

<blockquote>
  <p>To state a more general form of this result we introduce the following terminology.</p>
  
  <p><strong>Definition</strong>. $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)$.</p>
</blockquote>

<p>This class is actually a uniform version of AC.</p>

<p>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).</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-09-21T00:14:32.103Z
2012-09-21T00:14:32.103Z
Yuval Filmus
<p>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".</p>

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

<p>The $NC$ part of the story is documented, e.g., in <a href="http://en.wikipedia.org/wiki/NC_%28complexity%29" rel="nofollow noreferrer">Wikipedia</a> and in the complexity zoo, the story for $SC$ is told <a href="https://cstheory.stackexchange.com/questions/9298/steves-class-origin-of-sc">here</a>. </p>

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

<p>Does someone know who defined $AC$?</p>

CC BY-SA 3.0
2012-09-19T01:21:51.213Z
I just noticed the question about "Steve's class" (after Steven Cook) http://cstheory.stackexchange.com/questions/9298/steves-class-origin-of-sc?rq=1, and I think that maybe this was the class from the story, and not AC.
Dana Moshkovitz
CC BY-SA 3.0
2012-09-19T02:21:00.730Z
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..
Sasho Nikolov
CC BY-SA 3.0
2012-09-19T15:45:24.700Z
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...
Bruno
CC BY-SA 3.0
2012-09-20T23:04:41.063Z
There is no story behind it. A stands for alternation.
Tayfun Pay
<cc.complexity-theory><reference-request><ho.history-overview>
Who introduced the complexity class AC?
Dana Moshkovitz
# Who introduced the complexity class AC?

(Asked by: username_0 on 2012-09-19)

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](http://en.wikipedia.org/wiki/NC_%28complexity%29) and in the complexity zoo, the story for $SC$ is told [here](https://cstheory.stackexchange.com/questions/9298/steves-class-origin-of-sc).

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$?

**Tags:** cc.complexity-theory, reference-request, ho.history-overview
> **Comments:**
> **username_0**: I just noticed the question about "Steve's class" (after Steven Cook) http://cstheory.stackexchange.com/questions/9298/steves-class-origin-of-sc?rq=1, and I think that maybe this was the class from the story, and not AC.  
> **username_1**: 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..  
> **username_2**: 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...  
> **username_3**: There is no story behind it. A stands for alternation.  

---

## 1 answers

### Answer by username_4 on 2012-09-21. Score: 18 | Accepted answer

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.


---

