АСС0

ACC ⁰ , иногда называемый ACC , представляет собой класс вычислительных моделей и задач, определенных в сложности схем , области теоретической информатики. Класс определяется путем дополнения класса AC 0 «переменных схем» постоянной глубины способностью подсчета; аббревиатура ACC означает «AC со счетчиками». ^[1] В частности, задача относится к ACC ^{0 ,} если она может быть решена полиномиальными схемами постоянной глубины неограниченных вентилей с разветвлением, включая вентили, которые считают по модулю фиксированного целого числа. ACC ⁰ соответствует вычислению в любом разрешимом моноиде . Класс очень хорошо изучен в теоретической информатике из-за алгебраических связей и потому, что это одна из крупнейших конкретных вычислительных моделей, для которых могут быть доказаны результаты вычислительной невозможности, так называемые нижние границы схем.

Определения

Неформально ACC ⁰ моделирует класс вычислений, реализуемых булевыми схемами постоянной глубины и полиномиального размера, где вентили схемы включают «модульные счетные вентили», которые вычисляют количество истинных входов по модулю некоторой фиксированной константы.

Более формально, язык принадлежит AC ⁰ [ m ], если он может быть вычислен семейством схем C ₁ , C ₂ , ..., где C _n принимает n входов, глубина каждой схемы постоянна, размер C _n является полиномиальной функцией n , и схема использует следующие вентили: вентили AND и вентили OR неограниченного вентиля по входу , вычисляющие конъюнкцию и дизъюнкцию их входов; вентили NOT, вычисляющие отрицание их единственного входа; и вентили MOD- m неограниченного вентиля по входу, которые вычисляют 1, если количество входных единиц кратно m . Язык принадлежит ACC ⁰ , если он принадлежит AC ⁰ [ m ] для некоторого m .

В некоторых текстах ACC ⁱ относится к иерархии классов схем с ACC ⁰ на самом нижнем уровне, где схемы в ACC ⁱ имеют глубину O (log ⁱ n ) и полиномиальный размер. ^[1]

Класс ACC ⁰ также может быть определен в терминах вычислений неравномерных детерминированных конечных автоматов (NUDFA) над моноидами . В этой структуре входные данные интерпретируются как элементы из фиксированного моноида, и входные данные принимаются, если произведение входных элементов принадлежит заданному списку элементов моноида. Класс ACC ⁰ — это семейство языков, принимаемых NUDFA над некоторым моноидом, который не содержит неразрешимую группу в качестве подполугруппы. ^[2]

Вычислительная мощность

Класс ACC ⁰ включает AC 0 . Это включение является строгим, поскольку один вентиль MOD-2 вычисляет функцию четности, которую, как известно, невозможно вычислить в AC ⁰ . В более общем случае, функция MOD _m не может быть вычислена в AC ⁰ [ p ] для простого числа p , если только m не является степенью p . ^[3]

Класс ACC ⁰ включен в TC ^0. Предполагается, что ACC ⁰ не может вычислить функцию большинства своих входов (т. е. включение в TC ⁰ является строгим), но по состоянию на июль 2018 г. это остается нерешенным.

Каждая задача в ACC ⁰ может быть решена схемами глубины 2 с вентилями И полилогарифмического ветвления на входах, подключенными к одному вентилю, вычисляющему некоторую симметричную (не зависящую от порядка входов) функцию. ^[4] Эти схемы называются SYM ⁺ -схемами. Доказательство следует идеям доказательства теоремы Тоды .

Уильямс (2011) доказывает, что ACC ⁰ не содержит NEXPTIME . Доказательство использует множество результатов теории сложности, включая теорему об иерархии времени , IP = PSPACE , дерандомизацию и представление ACC ⁰ через схемы SYM ^{+ .}^[5] Мюррей и Уильямс (2018) улучшают эту границу и доказывают, что ACC ⁰ не содержит NQP (недетерминированное квазиполиномиальное время).

Известно, что вычисление перманента невозможно для LOGTIME -однородных схем ACC ⁰ , что означает, что класс сложности PP не содержится в LOGTIME-однородном ACC ⁰ . ^[6]

Примечания

^ ab Vollmer (1999), стр. 126
^ Териен (1981), Баррингтон и Териен (1988)
^ Разборов (1987), Смоленский (1987)
^ Бейгель и Таруи (1994)
^ Приложение к учебнику Ароры, Барака
^ Аллендер и Гор (1994)

Ссылки

Аллендер, Эрик (1996), «Сложность схем перед рассветом нового тысячелетия», 16-я конференция по основам программных технологий и теоретической информатики, Хайдарабад, Индия, 18–20 декабря 1996 г. , Lecture Notes in Computer Science, т. 1180, Springer, стр. 1–18, doi :10.1007/3-540-62034-6_33
Allender, Eric ; Gore, Vivec (1994), "A uniform circuit bottom bound for the permanent" (PDF) , SIAM Journal on Computing , 23 (5): 1026–1049, doi :10.1137/S0097539792233907, архивировано из оригинала (PDF) 2016-03-03 , извлечено 2012-07-02
Баррингтон, Д.А. (1989), «Программы ветвления полиномиального размера с ограниченной шириной распознают именно те языки, что в NC1» (PDF) , Журнал компьютерных и системных наук , 38 (1): 150–164, doi : 10.1016/0022-0000(89)90037-8.
Баррингтон, Дэвид А. Микс (1992), «Некоторые проблемы, связанные с полиномами Разборова-Смоленского», в Патерсон, М.С. (ред.), Сложность булевых функций, Sel. Pap. Symp., Дарем/Великобритания 1990. , Серия заметок лекций Лондонского математического общества, т. 169, стр. 109–128, ISBN 0-521-40826-1, ЗБЛ 0769.68041.
Баррингтон, ДА; Териен, Д. (1988), «Конечные моноиды и тонкая структура NC ¹ », Журнал ACM , 35 (4): 941–952, doi : 10.1145/48014.63138 , S2CID 52148641
Бейгель, Ричард; Таруи, Джун (1994), «Об ACC», Computational Complexity , 4 (4): 350–366, doi :10.1007/BF01263423, S2CID 2582220.
Clote, Peter; Kranakis, Evangelos (2002), Булевы функции и модели вычислений , Тексты по теоретической информатике. Серия EATCS, Берлин: Springer-Verlag , ISBN 3-540-59436-1, ЗБЛ 1016.94046
Разборов, А.А. (1987), "Нижние оценки мощности схем ограниченной глубины с базисом {⊕,∨}", Матем. записки АН СССР , 41 (4): 333–338.
Смоленский, Р. (1987), «Алгебраические методы в теории нижних оценок сложности булевых схем», Труды 19-го симпозиума ACM по теории вычислений , стр. 77–82, doi : 10.1145/28395.28404.
Мюррей, Коди Д.; Уильямс, Райан (2018), «Нижние границы схем для недетерминированного квазиполивремени: простая лемма о свидетеле для NP и NQP», Труды 50-го симпозиума ACM по теории вычислений , стр. 890–901, doi : 10.1145/3188745.3188910, hdl : 1721.1/130542 , S2CID 3685013
Териен, Д. (1981), «Классификация конечных моноидов: языковой подход», Теоретическая информатика , 14 (2): 195–208, doi :10.1016/0304-3975(81)90057-8.
Фолльмер, Хериберт (1999), Введение в сложность схем , Берлин: Springer, ISBN 3-540-64310-9.
Уильямс, Райан (2011), «Нижние границы неоднородных цепей ACC», 2011 IEEE 26-я ежегодная конференция по вычислительной сложности (PDF) , стр. 115–125, doi :10.1109/CCC.2011.36, ISBN 978-1-4577-0179-5.