Теорема о разрыве
- См. также Теорему о пробеле (значения) для других теорем о пробелах в математике .
В теории сложности вычислений теорема о пробелах, также известная как теорема Бородина–Трахтенброта о пробелах, является основной теоремой о сложности вычислимых функций . [1]
По сути, он утверждает, что в иерархии классов сложности существуют сколь угодно большие вычислимые пробелы . Для любой вычислимой функции , которая представляет увеличение вычислительных ресурсов , можно найти такую границу ресурса, что набор функций, вычислимых в пределах расширенной границы ресурса, совпадает с набором, вычислимым в пределах исходной границы.
Теорему независимо доказал Борис Трахтенброт. [2] и Аллан Бородин . [3] [4] Хотя вывод Трахтенброта на несколько лет опередил вывод Бородина, он не был известен и не признавался на Западе до тех пор, пока работа Бородина не была опубликована.
Теорема о разрыве
[ редактировать ]Общий вид теоремы следующий.
- Предположим, что Φ — абстрактная (Блюма) мера сложности . Для любой тотальной вычислимой функции g , для которой для каждого x существует полная вычислимая функция t такая, что относительно Φ с классы сложности граничными функциями t и идентичны.
Теорему можно доказать, используя аксиомы Блюма, без какой-либо ссылки на конкретную вычислительную модель , поэтому она применима ко времени, пространству или любой другой разумной мере сложности.
Для частного случая временной сложности это можно сформулировать проще:
- для любой полной вычислимой функции такой, что для всех x существует ограничение по времени такой, что .
Поскольку граница может быть очень большим (и часто будет неконструируемым ), теорема о разрыве не предполагает ничего интересного для таких классов сложности, как P или NP, [5] и это не противоречит теореме об иерархии времени или теореме об иерархии пространства . [6]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Пока, Лэнс; Гомер, Стив (июнь 2003 г.). «Краткая история сложности вычислений» (PDF) . Бюллетень Европейской ассоциации теоретической информатики (80): 95–133. Архивировано из оригинала (PDF) 29 декабря 2005 г.
- ^ Трахтенброт, Борис А. (1967). Сложность алгоритмов и вычислений (конспект лекций) . Новосибирский университет.
- ^ Бородин, Аллан (1969). «Классы сложности рекурсивных функций и существование пробелов в сложности». Фишер, Патрик К.; Гинзбург, Сеймур; Харрисон, Майкл А. (ред.). Материалы 1-го ежегодного симпозиума ACM по теории вычислений, 5–7 мая 1969 г., Марина-дель-Рей, Калифорния, США . Ассоциация вычислительной техники. стр. 67–78.
- ^ Бородин, Аллан (январь 1972 г.). «Вычислительная сложность и существование пробелов в сложности» . Журнал АКМ . 19 (1): 158–174. дои : 10.1145/321679.321691 . hdl : 1813/5899 .
- ^ Аллендер, Эрик В .; Луи, Майкл С.; Риган, Кеннет В. (2014). «Глава 7: Теория сложности». В Гонсалесе, Теофило ; Диас-Эррера, Хорхе; Такер, Аллен (ред.). Справочник по вычислительной технике, третье издание: Информатика и разработка программного обеспечения . ЦРК Пресс. п. 7-9. ISBN 9781439898529 .
К счастью, феномен разрыва не может произойти в течение определенного периода времени , который мог бы когда-либо интересовать кого-либо
. - ^ Зиманд, Мариус (2004). Вычислительная сложность: количественная перспектива . Математические исследования Северной Голландии. Том. 196. Эльзевир. п. 42. ИСБН 9780080476667 . .