АКК⁰ - ACC0 - Wikipedia

Набросок ACC-цепи: Для фиксированного числа m схема состоит из НЕ-, И-, ИЛИ- и (Mod m) -гейтов. Разветвление каждого элемента ограничено полиномом, а глубина схемы ограничена константой.

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

Определения

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

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

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

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

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

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

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

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

Уильямс (2011) доказывает, что ACC⁰ не содержит NEXPTIME. Доказательство использует многие результаты теории сложности, в том числе теорема об иерархии времени, IP = PSPACE, дерандомизация, а представление ACC⁰ через SYM⁺ схемы.^[5]

Известно, что вычисление постоянного невозможно для ВРЕМЯ -унифицированный ACC⁰ схем, из чего следует, что класс сложности PP не содержится в ACC, унифицированном для LOGTIME⁰.^[6]

Примечания

1. Фоллмер (1999), п. 126
2. Териен (1981), Баррингтон и Териен (1988)
3. Разборов (1987), Смоленский (1987)
4. Бейгель и Таруи (1994)
5. Приложение к Ароре, учебник Барака
6. Аллендер и Гор (1994)

Рекомендации

• Аллендер, Эрик (1996), «Сложность схемы перед рассветом нового тысячелетия», 16-я конференция по основам программных технологий и теоретической информатики, Хайдарабад, Индия, 18–20 декабря 1996 г. (PDF), Конспект лекций по информатике, 1180, Springer, стр. 1–18, Дои:10.1007/3-540-62034-6_33
• Аллендер, Эрик; Гор, Вивек (1994), «Единая схема нижней границы для перманента» (PDF), SIAM Журнал по вычислениям, 23 (5): 1026–1049, Дои:10.1137 / S0097539792233907
• Баррингтон, Д.А. (1989), "Программы ветвления с полиномиальным размером ограниченной ширины распознают именно эти языки в ЧПУ.¹" (PDF), Журнал компьютерных и системных наук, 38 (1): 150–164, Дои:10.1016/0022-0000(89)90037-8.
• Баррингтон, Дэвид А. Микс (1992), "Некоторые проблемы, связанные с полиномами Разборова-Смоленского", в Патерсон, М. (ред.), Сложность булевой функции, сел. Пап. Symp., Дарем / Великобритания, 1990., Серия лекций Лондонского математического общества, 169, стр. 109–128, ISBN  0-521-40826-1, Zbl  0769.68041.
• Barrington, D.A .; Териен, Д. (1988), "Конечные моноиды и тонкая структура NC¹", Журнал ACM, 35 (4): 941–952, Дои:10.1145/48014.63138
• Бейгель, Ричард; Таруи, июн (1994), "На ACC", Вычислительная сложность, 4: 350–366, Дои:10.1007 / BF01263423.
• Клот, Петр; Кранакис, Евангелос (2002), Логические функции и модели вычислений, Тексты по теоретической информатике. Серия EATCS, Берлин: Springer-Verlag, ISBN  3-540-59436-1, Zbl  1016.94046
• Разборов, А.А. (1987), "Нижние оценки размера схем ограниченной глубины с базой {⊕, ∨}", Математика. записки АН СССР, 41 (4): 333–338.
• Смоленский Р. (1987), "Алгебраические методы в теории нижних оценок сложности булевых схем", Proc. 19-й симпозиум ACM по теории вычислений, стр. 77–82, Дои:10.1145/28395.28404.
• Териен, Д. (1981), "Классификация конечных моноидов: языковой подход", Теоретическая информатика, 14 (2): 195–208, Дои:10.1016/0304-3975(81)90057-8.
• Фоллмер, Хериберт (1999), Введение в сложность схемы, Берлин: Springer, ISBN  3-540-64310-9.
• Уильямс, Райан (2011), "Неравномерные нижние границы цепи ACC" (PDF), Конференция IEEE по вычислительной сложности: 115–125, Дои:10.1109 / CCC.2011.36.