WikiDer > Экспоненциальная иерархия

Exponential hierarchy

В теория сложности вычислений, то экспоненциальная иерархия это иерархия классы сложности, что является экспоненциальное время аналог полиномиальная иерархия. Как и везде в теории сложности, «экспонента» используется в двух разных значениях (линейные экспоненциальные границы для постоянного c, и полные экспоненциальные оценки ), что приводит к двум версиям экспоненциальной иерархии.[1][2]

EH

EH - объединение классов для всех k, где (т.е. языки, вычислимые в недетерминированный время для некоторой постоянной c с оракул). Один также определяет

Эквивалентное определение: язык L в тогда и только тогда, когда это можно записать в виде

где вычислимый во времени предикат (что неявно ограничивает длину yя). Точно так же EH - это класс языков, вычислимых на переменная машина Тьюринга во время для некоторых c с постоянно множеством чередований.

EXPH

EXPH - это объединение классов , где (языки, вычислимые за недетерминированное время для некоторой постоянной c с оракул), и снова:

Язык L в тогда и только тогда, когда это можно записать как

где вычислимо во времени для некоторых c, что снова неявно ограничивает длину yя. Эквивалентно EXPH - это класс языков, вычислимых во времени. на переменной машине Тьюринга с постоянно множеством чередований.

Сравнение

ENE ⊆ EH ⊆ ESPACE,
EXPNEXP ⊆ EXPH ⊆ EXPSPACE,
EH ⊆ EXPH.

использованная литература

  1. ^ Сара Мокас, Отделение классов в иерархии экспоненциального времени от классов в PH, Теоретическая информатика 158 (1996), вып. 1–2, с. 221–231.
  2. ^ Анудж Давар, Георг Готтлоб, Лаури Хелла, Захват релятивизированных классов сложности без порядка, Mathematical Logic Quarterly 44 (1998), нет. 1. С. 109–122.

внешние ссылки

Зоопарк сложности: Класс EH