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

17

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

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

часть истории документирована, например, в Википедии и в сложности зоопарка, история для S C сказано здесь .NСSС

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

Знает ли кто - то , кто определил ?AС

Дана Мошковиц
источник
6
Я только что заметил вопрос о «классе Стива» (после Стивена Кука) cstheory.stackexchange.com/questions/9298/… , и я думаю, что, возможно, это был класс из истории, а не AC.
Дана Мошковиц
2
Насколько я могу судить, Furst, Saxe и Sipser не дают имени AC0. Но одно из их основных приложений - это отделение PSPACE от PH (= языки, вычисляемые чередующимися машинами с постоянным числом чередований) относительно оракула. Может быть, AC исходит из приложения чередующихся ТМ ..
Сашо Николов
1
По словам Ника Пиппенгера (см. Вопрос, связанный Даной в комментарии), имена SC и NC появились в Университете Торонто, когда Пиппенгер посещал группу Theory, к которой принадлежит Стив Кук. Другой известный теоретик в Торонто - Аллан Бородин. Может ли АС выступать за класс Аллана, чтобы он не ревновал? Я мог бы быть бессвязным ...
Бруно
За этим нет истории. А означает чередование.
Тайфун платят

Ответы:

18

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

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

AСККзнак равно1,2,...О(журналN)О(журналКN)

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

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

AСКNСК+1

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

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