АСС 0
АСС 0 , иногда называемый ACC , представляет собой класс вычислительных моделей и задач, определяемых сложностью схем , областью теоретической информатики. Класс определяется путем расширения класса AC. 0 «переменных контуров» постоянной глубины с возможностью счета; аббревиатура ACC означает «AC со счетчиками». [1] Конкретно проблема принадлежит ACC. 0 если ее можно решить с помощью схем постоянной глубины и полиномиального размера с неограниченными вентилями с разветвлением, включая вентили, которые считают по модулю фиксированного целого числа. АСС 0 соответствует вычислению в любом разрешимом моноиде . Этот класс очень хорошо изучен в теоретической информатике из-за алгебраических связей и потому, что это одна из крупнейших конкретных вычислительных моделей, для которых могут быть доказаны результаты вычислительной невозможности, так называемые нижние границы схемы.
Определения
[ редактировать ]Неофициально, АСС 0 моделирует класс вычислений, реализуемых логическими схемами постоянной глубины и полиномиального размера, где элементы схемы включают в себя «модульные счетные элементы», которые вычисляют количество истинных входных данных по модулю некоторой фиксированной константы.
Более формально язык принадлежит AC. 0 [ m ] если его можно вычислить с помощью семейства схем C 1 , C 2 , ..., где C n принимает n входов, глубина каждой схемы постоянна, размер C n является полиномиальной функцией от n , и схема использует следующие элементы: логические элементы И и логические элементы ИЛИ неограниченного разветвления , вычисляющие соединение и дизъюнкцию их входов; НЕ вентили, вычисляющие отрицание своего единственного входа; и неограниченные входные элементы MOD- m , которые вычисляют 1, если количество входных единиц кратно m . Язык принадлежит ACC 0 если он принадлежит AC 0 [ м ] для некоторого м .
В некоторых текстах АСС я относится к иерархии классов цепей с ACC 0 на самом нижнем уровне, где цепи в ACC я иметь глубину O (log я n ) и полиномиальный размер. [1]
Класс АСС 0 также может быть определен в терминах вычислений неоднородных детерминированных конечных автоматов (NUDFA) над моноидами . В этой структуре входные данные интерпретируются как элементы фиксированного моноида, и входные данные принимаются, если произведение входных элементов принадлежит заданному списку элементов моноида. Класс АСС 0 — это семейство языков, принимаемое NUDFA над некоторым моноидом, который не содержит неразрешимой группы в качестве подполугруппы. [2]
Вычислительная мощность
[ редактировать ]Класс АСС 0 включает переменный ток 0 . Это включение является строгим, поскольку один вентиль MOD-2 вычисляет функцию четности, которую, как известно, невозможно вычислить в AC. 0 . В более общем смысле, функция MOD m не может быть вычислена в AC. 0 [ p ] для простого числа p, если только m не является степенью числа p . [3]
Класс АСС 0 включен в ТК 0 . Предполагается, что АКК 0 не может вычислить мажоритарную функцию своих входных данных (т. е. включение в TC 0 является строгим), но по состоянию на июль 2018 года этот вопрос остается нерешенным.
Любая проблема в АСС 0 может быть решено с помощью схем глубины 2 с логическими элементами И полилогарифмического разветвления на входах, соединенными с одним логическим элементом, вычисляющим некоторую симметричную (не зависящую от порядка входов) функцию. [4] Эти схемы называются SYM. + -цепи. Доказательство следует идеям доказательства теоремы Тоды .
Уильямс (2011) доказывает, что АСС 0 не содержит NEXPTIME . В доказательстве используются многие результаты теории сложности, включая теорему об иерархии времени , IP = PSPACE , дерандомизацию и представление ACC. 0 через СИМ + схемы. [5] Мюррей и Уильямс (2018) улучшают эту оценку и доказывают, что ACC 0 не содержит NQP (недетерминированное квазиполиномиальное время).
Известно, что вычисление перманента невозможно для LOGTIME -равномерного ACC. 0 схем, из чего следует, что класс сложности PP не содержится в LOGTIME-унифицированном ACC 0 . [6]
Примечания
[ редактировать ]Ссылки
[ редактировать ]- Аллендер, Эрик (1996), «Сложность схемы перед рассветом нового тысячелетия» , 16-я конференция по основам программных технологий и теоретической информатики, Хайдарабад, Индия, 18–20 декабря 1996 г. , Конспекты лекций по информатике, том. 1180, Springer, стр. 1–18, номер документа : 10.1007/3-540-62034-6_33.
- Аллендер, Эрик ; Гор, Вивек (1994), «Нижняя граница постоянного контура для однородной схемы» (PDF) , SIAM Journal on Computing , 23 (5): 1026–1049, doi : 10.1137/S0097539792233907 , заархивировано из оригинала (PDF) в 2016 г. -03-03 , получено 2 июля 2012 г.
- Баррингтон, Д.А. (1989), «Программы ветвления полиномиального размера ограниченной ширины распознают именно эти языки в NC. 1 10.1016 / (PDF) , Журнал компьютерных и системных наук , 38 (1): 150–164, doi : 0022-0000(89)90037-8 .
- Баррингтон, Дэвид А. Микс (1992), «Некоторые проблемы, связанные с полиномами Разборова-Смоленского», в Патерсоне, М.С. (ред.), Сложность булевой функции, Sel. Пап. Symp., Дарем/Великобритания, 1990. , Серия конспектов лекций Лондонского математического общества, том. 169, стр. 109–128, ISBN. 0-521-40826-1 , Збл 0769.68041 .
- Баррингтон, Д.А.; Териен, Д. (1988), "Конечные моноиды и тонкая структура NC 1 ", Журнал ACM , 35 (4): 941–952, doi : 10.1145/48014.63138 , S2CID 52148641
- Бейгель, Ричард; Таруи, июнь (1994), «On ACC», Computational Complexity , 4 (4): 350–366, doi : 10.1007/BF01263423 , S2CID 2582220 .
- Клот, Питер; Кранакис, Евангелос (2002), Булевы функции и модели вычислений , Тексты по теоретической информатике. Серия EATCS, Берлин: Springer-Verlag , ISBN 3-540-59436-1 , Коллекция 1016.94046
- Разборов А.А. (1987), "Нижние оценки размера схем ограниченной глубины с базисом {⊕,∨}", Матем. Записки АН СССР , 41 (4): 333–338 .
- Смоленский Р. (1987), "Алгебраические методы в теории нижних оценок сложности булевых схем", Proc. 19-й симпозиум ACM по теории вычислений , стр. 77–82, doi : 10.1145/28395.28404 .
- Мюррей, Коди Д.; Уильямс, Райан (2018), «Нижние границы схемы для недетерминированного квазиполного времени: лемма простого свидетельства для NP и NQP», Proc. 50-й симпозиум ACM по теории вычислений , стр. 890–901, doi : 10.1145/3188745.3188910 , hdl : 1721.1/130542 , S2CID 3685013
- Териен, Д. (1981), «Классификация конечных моноидов: языковой подход», Theoretical Computer Science , 14 (2): 195–208, doi : 10.1016/0304-3975(81)90057-8 .
- Фоллмер, Гериберт (1999), Введение в сложность схем , Берлин: Springer, ISBN 3-540-64310-9 .
- Уильямс, Райан (2011), «Нижние границы неоднородной схемы ACC», 26-я ежегодная конференция IEEE по вычислительной сложности (PDF) , 2011 г. , стр. 115–125, doi : 10.1109/CCC.2011.36 , ISBN 978-1-4577-0179-5 .