ACC0 - Википедия - ACC0
АКК0иногда называют АКК, представляет собой класс вычислительных моделей и задач, определенных в сложность схемы, область теоретической информатики. Класс определяется путем расширения класса AC0 «чередующихся цепей» постоянной глубины с возможностью счета; аббревиатура ACC означает «кондиционер со счетчиками».[1] Конкретно проблема принадлежит ACC0 если это может быть решено схемами полиномиального размера с постоянной глубиной неограниченных входных вентилей, включая вентили, которые считают по модулю фиксированного целого числа. АКК0 соответствует вычислению в любой разрешимой моноид. Этот класс очень хорошо изучен в теоретической информатике из-за алгебраических связей и потому, что это одна из крупнейших конкретных вычислительных моделей, для которых могут быть доказаны результаты вычислительной невозможности, так называемые нижние границы схемы.
Определения
Неофициально, ACC0 моделирует класс вычислений, реализуемых булевыми схемами постоянной глубины и полиномиального размера, где вентили схемы включают «модульные счетные вентили», которые вычисляют количество истинных входов по модулю некоторой фиксированной константы.
Более формально язык принадлежит AC0[м], если его можно вычислить с помощью семейства схем C1, C2, ..., куда Cп берет п входов, глубина каждой цепи постоянна, размер Cп является полиномиальной функцией от п, а в схеме используются следующие вентили: И ворота и ИЛИ ворота неограниченного фан-ин, вычисляя соединение и дизъюнкцию их входов; НЕ ворота вычисление отрицания их единственного входа; и неограниченный веер MOD-м ворота, которые вычисляют 1, если количество входных единиц кратно м. Язык принадлежит ACC0 если он принадлежит AC0[м] для некоторых м.
В некоторых текстах ACCя относится к иерархии классов цепей с ACC0 на самом низком уровне, где цепи в ACCя иметь глубину О (бревнояп) и размер полинома.[1]
Класс ACC0 также можно определить в терминах вычислений неоднородных детерминированных конечных автоматов (NUDFA) над моноиды. В этой структуре входные данные интерпретируются как элементы из фиксированного моноида, и входные данные принимаются, если продукт входных элементов принадлежит заданному списку элементов моноида. Класс ACC0 это семейство языков, принимаемое NUDFA над некоторым моноидом, не содержащим неразрешимая группа как подполугруппа.[2]
Вычислительная мощность
Класс ACC0 включает AC0. Это включение является строгим, потому что один вентиль MOD-2 вычисляет функцию четности, которую, как известно, невозможно вычислить в AC.0. В более общем смысле функция MODм не может быть вычислен в AC0[п] для прайма п пока не м это сила п.[3]
Класс ACC0 входит в TC0. Предполагается, что ACC0 не может вычислить функция большинства его входов (т.е. включение в TC0 является строгим), но по состоянию на июль 2018 года этот вопрос не решен.
Каждая проблема в ACC0 может быть решена схемами глубины 2, с логическими элементами И полилогарифмического разветвления на входах, подключенными к одному элементу, вычисляющему симметричную функцию.[4] Эти схемы называются SYM.+-схемы. Доказательство следует идеям доказательства Теорема Тоды.
Уильямс (2011) доказывает, что ACC0 не содержит NEXPTIME. Доказательство использует многие результаты теории сложности, в том числе теорема об иерархии времени, IP = PSPACE, дерандомизация, а представление ACC0 через SYM+ схемы.[5]
Известно, что вычисление постоянного невозможно для ВРЕМЯ -унифицированный ACC0 схем, из чего следует, что класс сложности PP не содержится в ACC, унифицированном для LOGTIME0.[6]
Примечания
Рекомендации
- Аллендер, Эрик (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), "Программы ветвления с полиномиальным размером ограниченной ширины распознают именно эти языки в ЧПУ.1" (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), "Конечные моноиды и тонкая структура NC1", Журнал 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.