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

редактировать

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

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

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

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

$AC = ⋃ i ≥ 0 AC i {\ displaystyle {\ t_dv {AC}} = \ bigcup _ {i \ geq 0} {\ t_dv { AC}} ^ {i}}$ $\ t_dv {AC } = \ bigcup_ {i \ geq 0} \ t_dv {AC} ^ i$

Содержание

1 Отношение к NC
2 Варианты
3 Примечания
4 Ссылки

Отношение к NC

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

NC i ⊆ AC i ⊆ NC i + 1. {\ displaystyle {\ t_dv {NC}} ^ {i} \ substeq {\ t_dv {AC}} ^ {i} \ substeq {\ t_dv {NC}} ^ {i + 1}.}

\ t_dv {NC} ^ i \ substeq \ t_dv {AC} ^ i \ substeq \ t_dv {NC} ^ {i + 1}.

В качестве немедленного Как следствие этого, NC = AC.

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

Варианты

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

Notes

Ссылки

Arora, Sanjeev ; Барак, Боаз (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