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

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

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

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

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

Теорема о разрыве [ править ]

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

Предположим, что

Φ

- абстрактная мера сложности (Блюма) . Для любого полного вычислимой функции

г

, для которых для каждого

х

, существует общий вычислимая функция

т

таким образом, что по отношению к

Ф

, то классы сложности с граничными функциями

т

и являются идентичными.

{\ Displaystyle г (х) \ geq х}

{\ displaystyle g \ circ t}

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

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

для любой полной вычислимой функции такой, что для всех

x

существует временная граница, такая что .

{\ displaystyle g: \, \ omega \, \ to \, \ omega}

{\ Displaystyle г (х) \ geq х}

{\ Displaystyle Т (п)}

{\ displaystyle {\ mathsf {DTIME}} (g (T (n))) = {\ mathsf {DTIME}} (T (n))}

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

См. Также [ править ]

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

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

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

[1] Фортноу, Лэнс; Гомер, Стив (июнь 2003 г.). «Краткая история вычислительной сложности» (PDF) . Бюллетень Европейской ассоциации теоретической информатики (80): 95–133. Архивировано 29 декабря 2005 г. из оригинального (PDF) .

[2] Трахтенброт, Борис А. (1967). Сложность алгоритмов и вычислений (конспект лекций) . Новосибирский университет.

[3] Аллан Бородин (1969). «Классы сложности рекурсивных функций и наличие пробелов в сложности». Proc. 1-го ежегодного симпозиума ACM по теории вычислений : 67–78.

[4] Бородин, Аллан (январь 1972 г.). «Вычислительная сложность и наличие пробелов в сложности». Журнал ACM . 19 (1): 158–174. DOI : 10.1145 / 321679.321691 .

[5] Аллендер, Эрик В .; Луи, Майкл С .; Риган, Кеннет В. (2014), «Глава 7: Теория сложности», в Гонсалесе, Теофило ; Диас-Эррера, Хорхе; Такер, Аллен (ред.), Computing Handbook, Third Edition: Computer Science and Software Engineering , CRC Press, p. 7-9, ISBN 9781439898529, К счастью, разрыв явление не может произойти за время границ т , что кто - нибудь когда - либо быть заинтересованы в.

[6] Зиманд, Мариус (2004), Вычислительная сложность: количественная перспектива , Математические исследования Северной Голландии, 196 , Elsevier, p. 42, ISBN 9780080476667.

[1]