Кто ввел класс сложности AC?

Я учил нижних границ сегодня, и один из студентов спросил о причине названия . Официальное объяснение состоит в том, что «А» означает «Чередование». $AC^0$ $AC$

Я смутно помню, как много лет назад мне сказали, что ~~Ник Пиппенгер~~ Стив Кук назвал честь Ника Пиппенджера (класс Ника), а позже Ник назвал честь Стива (класс Стива). $NC$ $SC$

часть истории документирована, например, в Википедии и в сложности зоопарка, история для сказано здесь . $NC$ $SC$

Интересно, имеет ли похожую историю, но я не смог найти никаких ссылок на изобретателя $AC$ $AC$

Знает ли кто - то , кто определил ? $AC$

cc.complexity-theory reference-request ho.history-overview Дана Мошковиц
источник

Я только что заметил вопрос о «классе Стива» (после Стивена Кука) cstheory.stackexchange.com/questions/9298/… , и я думаю, что, возможно, это был класс из истории, а не AC.

Дана Мошковиц

Насколько я могу судить, Furst, Saxe и Sipser не дают имени AC0. Но одно из их основных приложений - это отделение PSPACE от PH (= языки, вычисляемые чередующимися машинами с постоянным числом чередований) относительно оракула. Может быть, AC исходит из приложения чередующихся ТМ ..

Сашо Николов

По словам Ника Пиппенгера (см. Вопрос, связанный Даной в комментарии), имена SC и NC появились в Университете Торонто, когда Пиппенгер посещал группу Theory, к которой принадлежит Стив Кук. Другой известный теоретик в Торонто - Аллан Бородин. Может ли АС выступать за класс Аллана, чтобы он не ревновал? Я мог бы быть бессвязным ...

Бруно

За этим нет истории. А означает чередование.

Тайфун платят

Ответы:

Я считаю, что обозначение AC впервые появляется в книге Кука "Таксономия проблем с быстрыми параллельными алгоритмами" от 1985 года. На странице 11 (страница 12 журнала) мы читаем:

Чтобы сформулировать более общую форму этого результата, введем следующую терминологию.

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

Этот класс на самом деле является единой версией AC.

Далее следует альтернативная характеристика Руццо и Томпы, появившаяся в техническом отчете Стокмейера и Вишкина, а затем в «Постоянной глубинной сводимости» Чандры, Стокмейера и Вишкина от 1984 года. Они используют обозначение SIZE-DEPTH (poly, constant) (см. стр. 3).

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

Во всех этих статьях много говорится о чередующихся машинах Тьюринга, что подтверждает гипотезу о том, что А означает чередование.

Юваль Фильмус
источник