Теорема о временной иерархии
-
Теоремы о временной иерархии
- Теоремы о временной иерархии описывают иерархию классов сложности, связанных с детерминированными и недетерминированными вычислениями.
- Они показывают, что существуют задачи, которые могут быть решены за полиномиальное время, но не за детерминированное экспоненциальное время.
- Эти теоремы являются ключевыми в теории сложности вычислений и имеют важные последствия для понимания сложности алгоритмов.
-
Доказательство теоремы о временной иерархии
- Доказательство основано на моделировании детерминированных машин Тьюринга на недетерминированных машинах.
- Оно показывает, что существует машина, которая может решить, принадлежит ли пара машина-вход к классу Hf за время, не превышающее f(m)3, где m — длина описания машины.
- Противоречие, возникающее при попытке построить машину, которая решает, принадлежит ли она сама к классу Hf, доказывает, что такой машины не существует.
-
Расширение теоремы
- В статье обсуждается, что доказательство дает более слабый результат, чем могло бы быть, из-за использования простой модели машины Тьюринга.
- Указывается, что существуют более эффективные модели, которые позволяют получить более точные результаты.
-
Последствия теоремы
- Теоремы о временной иерархии гарантируют, что экспоненциальная иерархия является подлинной иерархией.
- Они также показывают, что в классе P существуют задачи, требующие экспоненциального времени, но не могут быть решены за полиномиальное время.
- Теоремы не дают возможности связать детерминированную и недетерминированную сложность или сложность времени и пространства.
-
Более точные теоремы
- Существуют более точные теоремы, которые описывают разрыв между нижней и верхней временной рамками в теореме об иерархии.
- Они были получены для различных вычислительных моделей, таких как машина произвольного доступа и модель языка программирования.
-
Рекомендации
- Для дальнейшего чтения рекомендуется обратиться к страницам 310-313 раздела 9.1 и разделу 7.2.
Полный текст статьи: