АС (сложность)

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

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

Самый маленький класс переменного тока — переменный ток. ⁰ , состоящий из неограниченных веерных цепей постоянной глубины.

Общая иерархия классов AC определяется как

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

Отношение к NC

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

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

Непосредственным следствием этого является то, что NC = AC.

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

Вариации

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

Ссылки

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