В теоретической информатике , и , в частности теории сложности вычислений и схема сложности , ТС является сложность классом из задач принятия решения , которые могут быть признаны пороговыми схемами, которые являются булевыми схемами с И , ИЛИ , и мажоритарными воротами . Для каждого фиксированного i класс сложности TC i состоит из всех языков, которые могут быть распознаны семейством пороговых схем глубины, полиномиальный размер и неограниченное разветвление . Класс TC определяется через
Отношение к NC и AC
Отношения между TC, NC и иерархией AC можно резюмировать следующим образом:
В частности, мы знаем, что
Первое строгое ограничение следует из того факта, что NC 0 не может вычислить любую функцию, которая зависит от всех входных битов. Таким образом, выбор задачи, которая тривиально находится в AC 0 и зависит от всех битов, разделяет два класса. (Например, рассмотрим функцию ИЛИ.) Строгое сдерживание AC 0 ⊊ TC 0 следует, потому что четность и большинство (которые оба находятся в TC 0 ), как было показано, не находятся в AC 0 . [1] [2]
Как непосредственное следствие вышеупомянутых ограничений, мы имеем NC = AC = TC.
Рекомендации
- ^ Ферст, Меррик; Сакс, Джеймс Б .; Sipser, Майкл (1984), "Parity, схемы, и полином-иерархия по времени", Математическая теория систем , 17 (1): 13-27, DOI : 10.1007 / BF01744431 , МР 0738749.
- ^ Хастад, Йохан (1989), «Почти оптимальные нижние границы для схем малой глубины», в Микали, Сильвио (ред.), Случайность и вычисления (PDF) , Достижения в компьютерных исследованиях, 5 , JAI Press, стр. 6–20, ISBN 0-89232-896-7, архивировано из оригинального (PDF) 22.02.2012
- Фоллмер, Хериберт (1999). Введение в сложность схем . Берлин: Springer. ISBN 3-540-64310-9.