AC (сложность) - AC (complexity)

В сложности схем , переменный ток является класс сложности иерархии. Каждый класс, AC ^я , состоит из языков , признанных булевых схем с глубиной и полиномиальное число от неограниченную веера-в И и ИЛИ ворота . ${\ Displaystyle О (\ журнал ^ {я} п)}$

Название «AC» было выбрано по аналогии с NC , где «A» в названии означает «чередующийся» и относится как к чередованию между логическими элементами И и ИЛИ в схемах, так и к чередующимся машинам Тьюринга .

Наименьшим классом переменного тока является AC ⁰ , состоящий из контуров постоянной глубины и неограниченного втягивания.

Полная иерархия классов AC определяется как

${\ Displaystyle {\ mbox {AC}} = \ bigcup _ {я \ geq 0} {\ mbox {AC}} ^ {i}}$

Отношение к NC

Классы AC связаны с классами NC , которые определены аналогично, но с гейтами, имеющими только постоянный финиш. Для каждого i мы имеем

${\ displaystyle {\ mbox {NC}} ^ {i} \ substeq {\ mbox {AC}} ^ {i} \ substeq {\ mbox {NC}} ^ {i + 1}.}$

Как непосредственное следствие этого мы имеем NC = AC.

Известно, что включение строгое при i = 0.

Вариации

На мощность классов переменного тока можно повлиять добавлением дополнительных ворот. Если мы добавим элементы, которые вычисляют операцию по модулю для некоторого модуля m , мы получим классы ACC ⁱ [m] .

Ноты

Ссылки

• Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность. Современный подход , Cambridge University Press , ISBN 978-0-521-42426-4, Zbl  1193,68112
• Клот, Петр; Кранакис, Евангелос (2002), Булевы функции и модели вычислений , Тексты по теоретической информатике. Серия EATCS, Берлин: Springer-Verlag , ISBN 3-540-59436-1, Zbl  1016,94046
• Реган, Кеннет В. (1999), «Классы сложности», Справочник по алгоритмам и теории вычислений , CRC Press.
• Воллмер, Хериберт (1998), Введение в сложность схем. Единый подход , Тексты по теоретической информатике, Берлин: Springer-Verlag , ISBN 3-540-64310-9, Zbl  0931,68055