WikiDer > ТК (сложность)

TC (complexity)

В теоретическая информатика, и в частности теория сложности вычислений и сложность схемы, TC это класс сложности из проблемы решения которые могут быть распознаны пороговыми цепями, которые Булевы схемы с И, ИЛИ ЖЕ, и Ворота большинства. Для каждого фиксированного я, класс сложности TCя состоит из всех языков, которые могут быть распознаны семейством пороговых схем глубины , многочлен размер и неограниченный фан-ин. Класс TC определяется через

Отношение к NC и AC

Отношения между ТК, NC и AC иерархию можно резюмировать следующим образом:

В частности, мы знаем, что

Первое строгое сдерживание следует из того, что NC0 не может вычислить любую функцию, которая зависит от всех входных битов. Таким образом, выбирая задачу, которая тривиально находится в AC0 и зависит от всех битов, разделяющих два класса. (Например, рассмотрим функцию ИЛИ.) Строгое сдерживание AC0 ⊊ TC0 следует, потому что паритет и большинство (которые оба в TC0) были показаны не в AC0.[1][2]

Как непосредственное следствие вышеупомянутых ограничений, мы имеем NC = AC = TC.

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

  1. ^ Ферст, Меррик; Сакс, Джеймс Б.; Сипсер, Майкл (1984), "Четность, схемы и иерархия полиномиального времени", Математическая теория систем, 17 (1): 13–27, Дои:10.1007 / BF01744431, МИСТЕР 0738749.
  2. ^ Хостад, Йохан (1989), "Почти оптимальные нижние границы для схем малой глубины", в Микали, Сильвио (ред.), Случайность и вычисление (PDF), Достижения в области компьютерных исследований, 5, JAI Press, стр. 6–20, ISBN 0-89232-896-7, заархивировано из оригинал (PDF) на 2012-02-22
  • Фоллмер, Хериберт (1999). Введение в сложность схемы. Берлин: Springer. ISBN 3-540-64310-9.