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

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

Определения

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

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

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

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

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

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

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

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

Williams (2011) доказывает, что ACC 0 не содержит NEXPTIME . Доказательство использует множество результатов теории сложности, в том числе теорему об иерархии времени , IP = PSPACE , дерандомизацию и представление ACC 0 через схемы SYM + . [5] Murray & Williams (2018) улучшают эту оценку и доказывают, что ACC 0 не содержит NQP (недетерминированное квазиполиномиальное время).

Известно, что вычисление перманента невозможно для LOGTIME -равномерных ACC 0 схем, из чего следует, что класс сложности PP не содержится в LOGTIME-uniform ACC 0 . [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, doi : 10.1007/3-540-62034-6_33.
  • Аллендер, Эрик ; Гор, Вивек (1994), «Нижняя граница универсальной схемы для перманента» (PDF) , SIAM Journal on Computing , 23 (5): 1026–1049, doi : 10.1137 / S0097539792233907
  • Баррингтон, Д.А. (1989), «Ветвящиеся программы полиномиального размера с ограниченной шириной распознают именно эти языки в NC 1 » (PDF) , Journal of Computer and System Sciences , 38 (1): 150–164, doi : 10.1016/0022- 0000(89)90037-8.
  • Баррингтон, Дэвид А. Микс (1992), «Некоторые проблемы, связанные с полиномами Разборова-Смоленского», в Патерсон, М.С. (ред.), Сложность булевой функции, Sel. Пап. Symp., Дарем / Великобритания, 1990. , Серия конспектов лекций Лондонского математического общества, том. 169, стр. 109–128, ISBN . 0-521-40826-1, Збл  0769.68041.
  • Баррингтон, округ Колумбия; Териен, Д. (1988), «Конечные моноиды и тонкая структура NC 1 », Journal of the ACM , 35 (4): 941–952, doi : 10.1145/48014.63138
  • Бейгель, Ричард; Таруи, июнь (1994), «О ACC», Computational Complexity , 4 (4): 350–366, doi : 10.1007/BF01263423.
  • Клоте, Питер; Кранакис, Евангелос (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
  • Териен, Д. (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» (PDF) , Конференция IEEE по вычислительной сложности : 115–125, doi : 10.1109 / CCC.2011.36 , ISBN 978-1-4577-0179-5.
Получено с " https://en.wikipedia.org/w/index.php?title=ACC0&oldid=1036682727 "
Contribute a better translation