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

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

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

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

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

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

Отношение к NC

Классы AC относятся к NC классы, которые определены аналогично, но с гейтами, имеющими только постоянный fanin. Для каждого я, у нас есть^[2][3]

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

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

Известно, что включение строго при я = 0.^[3]

Вариации

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

Примечания

1. Риган (1999), стр. 27-18.
2. Клот и Кранакис (2002), п. 437)
3. Арора и Барак (2009), п. 118)
4. Клот и Кранакис (2002), п. 12)

Рекомендации

• Арора, Санджив; Варак, Вооз (2009), Вычислительная сложность. Современный подход, Издательство Кембриджского университета, 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