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

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

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

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

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

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

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

Предположим Φ является абстрактная мера сложности (Блюма). Для любого полная вычислимая функция г для которого для каждого Икс, существует полная вычислимая функция т так что в отношении Φ, то классы сложности с граничными функциями т и идентичны.

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

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

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

Потому что граница может быть очень большим (и часто будет нерушимый ) из теоремы о разрыве не следует ничего интересного для таких классов сложности, как 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.