ТК 0

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

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

ТК ⁰ содержит несколько важных задач, таких как сортировка n n -битных чисел, умножение двух n -битных чисел, целочисленное деление или распознавание языка Дейка с двумя типами круглых скобок.

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

Мы можем связать TC ⁰ к другим классам цепей, включая переменный ток ⁰ и Северная Каролина ¹ ; Воллмер 1999 с. 126 государств:

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

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

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

Основа единого ТК ⁰

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

Ссылки

• Аллендер, Э. (1996). «Заметка о нижних границах равномерной схемы для счетной иерархии». Материалы 2-й Международной конференции по вычислительной технике и комбинаторике (COCOON) . Конспекты лекций Springer по информатике . Том. 1090. стр. 127–135.
• Клот, Питер; Кранакис, Евангелос (2002). Булевы функции и модели вычислений . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . ISBN  3-540-59436-1 . Збл   1016.94046 .
• Воллмер, Гериберт (1999). Введение в сложность схемы. Единый подход . Тексты по теоретической информатике. Берлин: Springer-Verlag . ISBN  3-540-64310-9 . Збл   0931.68055 .
• Бурчик, Ханс-Йорг; Воллмер, Гериберт (1998). «Кванторы Линдстрема и определимость листового языка». Международный журнал основ компьютерных наук . 9 (3): 277–294. дои : 10.1142/S0129054198000180 . ЕССС   ТР96-005 .

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

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