В сложности схем , переменный ток является класс сложности иерархии. Каждый класс, AC я , состоит из языков , признанных булевых схем с глубиной и полиномиальное число от неограниченную веера-в И и ИЛИ ворота .
Название «AC» было выбрано по аналогии с NC , где «A» в названии означает «чередующийся» и относится как к чередованию между логическими элементами AND и OR в схемах, так и к чередующимся машинам Тьюринга . [1]
Наименьшим классом переменного тока является AC 0 , состоящий из контуров постоянной глубины с неограниченным включением вентилятора.
Полная иерархия классов AC определяется как
Отношение к NC [ править ]
Классы AC связаны с классами NC , которые определены аналогично, но с гейтами, имеющими только постоянное соединение. Для каждого i имеем [2] [3]
Как непосредственное следствие этого мы имеем NC = AC. [4]
Известно, что включение строгое при i = 0. [3]
Варианты [ править ]
На мощность классов переменного тока можно повлиять добавлением дополнительных ворот. Если мы добавим элементы, которые вычисляют операцию по модулю для некоторого модуля m , мы получим классы ACC i [m] . [4]
Заметки [ править ]
- ^ Риган (1999) , стр 27-18.
- ^ Clote & Kranakis (2002 , стр. 437)
- ^ а б Арора и Барак (2009 , с. 118)
- ^ a b Клот и Кранакис (2002 , стр.12 )
Ссылки [ править ]
- Арора, Санджив ; Барак, Боаз (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
