WikiDer > AC (сложность) - Википедия

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

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

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

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

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

Отношение к NC

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

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

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

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

Вариации

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

Примечания

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

• Арора, Санджив; Варак, Вооз (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