From Wikipedia, the free encyclopedia
Jump to: navigation, search


I propose to make this page about ACC0, i.e., the constant-depth version of ACC. The literature is confused about if ACC0 = ACC, but there are almost no papers written about ACC (except those that actually about ACC0). Revert me if you disagree. Thore Husfeldt (talk) 20:37, 18 November 2010 (UTC)

ACC as a hierarchy[edit]

A few days ago, this article was about ACC as a the union of a hierarchy of classes. The reference for that definition was Vollmer (p.126). I checked that reference, and Vollmer does not use ACC in that way, which is why I removed all mention of it when I unilaterally changed what this article should be about. (Another, perhaps better, reason is that ACC, defined as a hierarchy, coincides with AC (and TC and NC), so it’s a really bad class.) EmilJ put it back in, but now that usage is unsourced. I can’t find a good source myself, so: who uses ACC as the union of ACC^i ? Thore Husfeldt (talk) 10:21, 22 November 2010 (UTC)

I've always seen ACC used as a synonym of ACC^0. --Robin (talk) 15:43, 22 November 2010 (UTC)
Hmm. I can't find any source either, now that you mention it. I basically restored the sentence to be on the safe side, but maybe it's better to delete it after all.—Emil J. 15:56, 22 November 2010 (UTC)