ТК 0

TC ⁰ - это класс сложности, используемый для сложности схемы . Это первый класс в иерархии классов TC .

TC ⁰ содержит все языки , которые решаются булевыми схемами с постоянной глубиной и полиномиального размером, содержащим только неограниченные веерными в И воротах , ИЛИ ворота , НЕ ворота и мажоритарные ворота . Аналогично, пороговые ворота могут использоваться вместо ворот большинства.

TC ⁰ содержит несколько важных проблем, таких как сортировка n n -битных чисел, умножение двух n -битных чисел, целочисленное деление ^[1] или распознавание языка Дейка с двумя типами скобок.

Отношения классов сложности [ править ]

Мы можем связать TC ⁰ с другими классами схем, включая AC ⁰ и NC ¹ ; Фоллмер 1999 стр. 126 утверждает:

${\ Displaystyle {\ mbox {AC}} ^ {0} \ subsetneq {\ mbox {AC}} ^ {0} [p] \ subsetneq {\ mbox {TC}} ^ {0} \ substeq {\ mbox {NC }} ^ {1}.}$

Фоллмер заявляет, что вопрос о том, является ли последнее включение строгим, является «одной из основных открытых проблем в сложности схем» (там же).

У нас также есть эта форма . (Allender 1996, цитируется по Burtschick 1999).${\ Displaystyle {\ mbox {TC}} ^ {0} \ subsetneq {\ mbox {PP}}}$

Основа униформы ${\ displaystyle {\ mbox {TC}} ^ {0}}$[ править ]

Функциональная версия равномерных совпадает с замыканием по отношению к композиции выступов и один из следующих наборов функций , . ^[2] Здесь , является побитовое И и . Под функциональной версией понимается множество всех функций над неотрицательными целыми числами, которые ограничены функциями FP и находятся в униформе .${\ displaystyle {\ mbox {TC}} ^ {0}}$${\ displaystyle \ {n + m, n \, {\ stackrel {.} {-}} \, m, n \ wedge m, \ lfloor n / m \ rfloor, 2 ^ {\ lfloor \ log _ {2} n \ rfloor ^ {2}} \}}$${\ displaystyle \ {n + m, n \, {\ stackrel {.} {-}} \, m, n \ wedge m, \ lfloor n / m \ rfloor, n ^ {\ lfloor \ log _ {2} м \ rfloor} \}}$${\ Displaystyle п \, {\ stackrel {.} {-}} \, m = \ max (0, нм)}$${\ Displaystyle п \ клин м}$${\displaystyle n}$${\displaystyle m}$${\displaystyle f(x_{1},\ldots ,x_{n})}$${\displaystyle (y{\text{-th bit of }}f(x_{1},\ldots ,x_{n}))}$${\displaystyle {\mbox{TC}}^{0}}$

Ссылки [ править ]

• Аллендер, Э. (1996). «Примечание о нижних границах единой схемы для счетной иерархии». Труды 2-й Международной конференции по вычислительной и комбинаторике (COCOON) . Springer Lecture Notes в области компьютерных наук . 1090 . С. 127–135.
• Клот, Петр; Кранакис, Евангелос (2002). Булевы функции и вычислительные модели . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . ISBN 3-540-59436-1. Zbl  1016.94046 .
• Фоллмер, Хериберт (1999). Введение в сложность схем. Единый подход . Тексты по теоретической информатике. Берлин: Springer-Verlag . ISBN 3-540-64310-9. Zbl  0931.68055 .
• Burtschick, Hans-Jörg; Фоллмер, Хериберт (1999). «Квантификаторы Линдстрема и определяемость языка листьев». ECCC  TR96-005 . Cite journal requires |journal= (help)

Внешние ссылки [ править ]

• Зоопарк сложности : TC 0