TC0

Класс сложности, используемый в сложности схемы

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

TC ⁰ содержит все языки, которые определяются булевыми схемами с постоянной глубиной и полиномиальным размером, содержащими только неограниченные вентили AND , OR , NOT и мажоритарные вентили . Эквивалентно, пороговые вентили могут использоваться вместо мажоритарных вентилей.

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

Отношения класса сложности

Мы можем связать TC ⁰ с другими классами цепей, включая AC 0 и NC 1 ; Vollmer 1999 стр. 126 утверждает:

${\displaystyle {\mathsf {AC}}^{0}\subsetneq {\mathsf {AC}}^{0}[p]\subsetneq {\mathsf {TC}}^{0}\subseteq {\mathsf {NC}}^{1}.}$

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

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

Основа для единого ТС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}m\rfloor }\}}$ ${\displaystyle n\,{\stackrel {.}{-}}\,m=\max(0,n-m)}$ ${\displaystyle n\wedge m}$ ${\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}}$

Ссылки

1. Хессе, Уильям; Аллендер, Эрик; Микс Баррингтон, Дэвид (2002). «Равномерные пороговые схемы постоянной глубины для деления и итерационного умножения». Журнал компьютерных и системных наук . 65 (4): 695–716. doi : 10.1016/S0022-0000(02)00025-9 .
2. Волков, Сергей. (2016). «Конечные базисы относительно суперпозиции в классах элементарных рекурсивных функций», диссертация. arXiv : 1611.04843 [cs.CC].

• Аллендер, Э. (1996). «Заметка о нижних границах равномерных схем для иерархии подсчета». Труды 2-й Международной конференции по вычислениям и комбинаторике (COCOON) . Springer Lecture Notes in Computer Science . Vol. 1090. pp. 127–135.
• Clote, Peter; Kranakis, Evangelos (2002). Булевы функции и модели вычислений . Тексты по теоретической информатике. Серия EATCS. ​​Берлин: Springer-Verlag . ISBN 3-540-59436-1. Збл  1016.94046.
• Фолльмер, Хериберт (1999). Введение в сложность схем. Единый подход . Тексты по теоретической информатике. Берлин: Springer-Verlag . ISBN 3-540-64310-9. Збл  0931.68055.
• Burtschick, Hans-Jörg; Vollmer, Heribert (1998). «Квантификаторы Линдстрема и определимость листового языка». International Journal of Foundations of Computer Science . 9 (3): 277–294. doi :10.1142/S0129054198000180. ECCC  TR96-005.

Внешние ссылки

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