TC0 - TC0

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

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

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

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

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

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

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

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

Основа для униформы ${displaystyle {mbox {TC}} ^ {0}}$

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

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

• Аллендер, Э. (1996). «Заметка о нижних границах единой схемы для счетной иерархии». Труды 2-й Международной конференции по вычислительной и комбинаторике (COCOON). Springer Конспект лекций по информатике. 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. Цитировать журнал требует | журнал = (помощь)

внешняя ссылка

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