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

Формулировка

Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций [math]f[/math] и [math]g[/math] таких, что [math] \lim_{n \rightarrow \infty} f(n)/g(n) = 0[/math], выполняется [math]DSPACE(g(n)) \ne DSPACE(f(n))[/math].

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

Зафиксируем [math]f[/math] и [math]g[/math].

Рассмотрим язык [math]L = \{ \lt m,x\gt \mid m(\lt m,x\gt )[/math] не допускает, используя не более [math] f(|\lt m,x\gt |)[/math] памяти [math]\}[/math] .

Пусть [math]L \in DSPACE(f)[/math], тогда для него есть машина тьюринга [math]m_0[/math] такая, что [math]L(m_0)=L[/math].

Рассмотрим [math]m_0(\lt m_0,x\gt )[/math].

Пусть [math]m_0[/math] допускает [math]\lt m_0,x\gt [/math]. Тогда [math]\lt m_0,x\gt \in L[/math], но в [math]L[/math] по определению не может быть пары [math]\lt m,x\gt [/math], которую допускает [math]m[/math]. Таким образом, получаем противоречие.

Если [math]m_0[/math] не допускает [math]\lt m_0,x\gt [/math], то [math]\lt m_0,x\gt [/math] не принадлежит языку [math]L[/math]. Это значит, что либо [math]m_0[/math] допускает [math]\lt m_0,x\gt [/math], либо не допускает, используя памяти больше [math]f(|\lt m_0,x\gt |)[/math]. Но [math]L \in DSPACE(f)[/math], поэтому [math]m_0[/math] на любом входе [math]x[/math] использует не более [math]f(|x|)[/math] памяти. Получаем противоречие.

Следовательно такой машины не существует. Таким образом, [math]L \notin DSPACE(f)[/math].

[math]L \in DSPACE(g)[/math], так как можно проэмулировать [math]m[/math].

Получается, что [math]L \in DSPACE(g(n)) \ DSPACE(f(n))[/math].

Теорема доказана.