Теоремы о временной и ёмкостной иерархиях

Эта статья находится в разработке!

Теорема (О емкостной иерархии):

Пусть даны две конструируемые по памяти функции [math]f[/math] и [math]g[/math] такие, что [math]\lim \limits_{n\rightarrow\infty} \frac{f(n)}{g(n)}=0[/math], тогда [math]DSPACE(g(n))\neq DSPACE(f(n))[/math].

Доказательство:

[math]\triangleright[/math]

Для доказательства воспользуемся диагональным методом. Рассмотрим функцию [math]h(n)=\sqrt{f(n)g(n)}[/math]. Докажем, что [math]L=\{x|x(x)\Bigr|_{s\leq O(h(|x|))}\neq 1\}\in DSPACE(g(n))\setminus DSPACE(f(n))[/math]. Иначе говоря, [math]L[/math] — это язык программ, которые не возвращают 1 на собственном входе при условии ограничения на память [math]O(h(|x|))[/math]. Очевидно, что [math]L \in DSPACE(g(n))[/math]. Предположим теперь, что [math]L \in DSPACE(f(n))[/math]. Тогда существует программа [math]p[/math], распознающая язык [math]L[/math] и использующая не более [math]c \cdot f(n)[/math] памяти. Т. к. [math]f(n)=o(h(n))[/math], то [math]\exists n_0: \forall n\gt n_0~c\cdot f(n)\lt h(n)[/math]. Будем считать, что [math]|p|\gt n_0[/math] (иначе добавим в программу пустые строки, искусственно увеличив её длину). Выясним, принадлежит ли [math]p[/math] языку [math]L[/math]. Допустим, что [math]p\in L[/math], тогда [math]p(p)=1[/math], причём ответ будет посчитан за время [math]O(h(n))[/math], значит, по определению [math]p\notin L[/math]. Пусть теперь [math]p\notin L[/math]. Но тогда по определению языка [math]p(p)=1[/math], значит, [math]p\in L[/math]. Таким образом, язык [math]L[/math] не может быть из [math]DSPACE(f(n))[/math], следовательно, язык из [math]DSPACE(g(n))\setminus DSPACE(f(n))[/math] найден.

[math]\triangleleft[/math]