Экспоненциальная иерархия
-
Экспоненциальная иерархия сложности
- Экспоненциальная иерархия представляет собой экспоненциальное расширение полиномиальной иерархии.
- Существует два типа экспоненциальных границ: линейные экспоненциальные и полные экспоненциальные.
- Класс сложности EH объединяет все языки, которые могут быть вычислены за недетерминированное время 2cn для некоторой константы c и оракула Σk-1P.
- Язык L принадлежит классу EH, если его можно записать в виде R(x, y1, …, yn), где R(x, y1, …, yn) вычислим во времени 2cn для некоторого c.
-
Класс сложности EXPH
- EXPH объединяет все языки, которые могут быть вычислены за недетерминированное время 2n^c для некоторой константы c и оракула Σk-1P.
- Язык L принадлежит классу EXPH, если его можно записать в виде R(x, y1, …, yk), где R(x, y1, …, yk) вычислим во времени 2|x|^c для некоторого c.
- Эквивалентно, EXPH — это класс языков, которые могут быть вычислены во времени 2n^c на переменной машине Тьюринга с постоянным количеством чередований.
Полный текст статьи: