Теорема о разрыве - Gap theorem

Смотрите также Теорема о разрыве (значения) для других теорем о разрыве в математика.

В теория сложности вычислений, то Теорема о разрыве, также известный как Теорема Бородина – Трахтенброта о щели, основная теорема о сложности вычислимые функции.^[1]

По сути, он утверждает, что существуют сколь угодно большие вычислимые пробелы в иерархии классы сложности. Для любого вычислимая функция что представляет собой увеличение вычислительные ресурсы, можно найти такую ​​привязку к ресурсу, чтобы набор функций, вычисляемых в рамках расширенной границы ресурса, был таким же, как набор вычислимых в пределах исходной границы.

Теорема была независимо доказана Борис Трахтенброт^[2] и Аллан Бородин.^[3][4]Хотя вывод Трахтенброта на несколько лет предшествовал возникновению Бородина, он не был известен и не признавался в Запад пока не было опубликовано произведение Бородина.

Теорема о разрыве

Общий вид теоремы следующий.

Предположим Φ является абстрактная мера сложности (Блюма). Для любого полная вычислимая функция г для которого ${\displaystyle g(x)\geq x}$ для каждого Икс, существует полная вычислимая функция т так что в отношении Φ, то классы сложности с граничными функциями т и ${\displaystyle g\circ t}$ идентичны.

Теорема может быть доказана с использованием аксиом Блюма без какой-либо ссылки на конкретную вычислительная модель, поэтому он применяется к времени, пространству или любой другой разумной мере сложности.

Для особого случая временной сложности это можно описать проще:

для любой полной вычислимой функции ${\displaystyle g:\,\omega \,\to \,\omega }$ такой, что ${\displaystyle g(x)\geq x}$ для всех Икс, существует ограничение по времени ${\displaystyle T(n)}$ такой, что ${\displaystyle {\mathsf {DTIME}}(g(T(n)))={\mathsf {DTIME}}(T(n))}$.

Потому что граница ${\displaystyle T(n)}$ может быть очень большим (и часто будет нерушимый ) из теоремы о разрыве не следует ничего интересного для таких классов сложности, как P или NP,^[5] и это не противоречит теорема об иерархии времени или теорема пространственной иерархии.^[6]

Смотрите также

• Теорема Блюма об ускорении

использованная литература

1. Фортноу, Лэнс; Гомер, Стив (июнь 2003 г.). «Краткая история вычислительной сложности» (PDF). Бюллетень Европейской ассоциации теоретической информатики (80): 95–133. Архивировано из оригинал (PDF) на 2005-12-29.
2. Трахтенброт, Борис А. (1967). Сложность алгоритмов и вычислений (конспекты лекций). Новосибирский университет.
3. Аллан Бородин (1969). «Классы сложности рекурсивных функций и наличие пробелов в сложности». Proc. 1-го ежегодного симпозиума ACM по теории вычислений: 67–78.
4. Бородин, Аллан (январь 1972 г.). «Вычислительная сложность и наличие пробелов в сложности». Журнал ACM. 19 (1): 158–174. Дои:10.1145/321679.321691.
5. Аллендер, Эрик В.; Луи, Майкл С .; Риган, Кеннет В. (2014), «Глава 7: Теория сложности», в Гонсалес, Теофило; Диас-Эррера, Хорхе; Такер, Аллен (ред.), Справочник по вычислениям, третье издание: компьютерные науки и программная инженерия, CRC Press, стр. 7-9, ISBN  9781439898529, К счастью, феномен разрыва не может произойти в ограниченные сроки. т что кому-нибудь когда-нибудь будет интересно.
6. Зиманд, Мариус (2004), Вычислительная сложность: количественная перспектива, Математические исследования Северной Голландии, 196, Elsevier, стр. 42, ISBN  9780080476667.