Материал из Викиконспекты
| Определение: |
| Функция [math]f(x)[/math] называется конструируемой по памяти, если можно вычислить [math]f(x)[/math] по [math]x[/math], используя не более [math]f(x)[/math] памяти. |
| Теорема (о емкостной иерархии): |
Пусть даны две конструируемые по памяти функции [math]f[/math] и [math]g[/math] такие, что [math]\lim \limits_{n\rightarrow\infty} \frac{f(n)}{g(n)}=0[/math], тогда [math]DSPACE(f(n)) \varsubsetneq DSPACE(g(n))[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Очевидно, что [math]DSPACE(f(n)) \subseteq DSPACE(g(n))[/math], поскольку программа, ограниченная по памяти финкцией [math]f[/math], проходит ограничение [math]g[/math].
Используя диагональный метод, докажем, что включение строгое. Рассмотрим функцию [math]h(n)=\sqrt{f(n)g(n)}[/math] и язык [math]L=\{x|x(x)\Bigr|_{S\leq h(|x|)}\neq 1\}[/math], где запись [math]S\leq h(|x|)[/math] означает, что программа запускается с лимитом памяти [math]h(|x|)[/math]. Иначе говоря, [math]L[/math] — это язык программ, которые не допускают собственный код, используя памяти не более [math]h(|x|)[/math]. Докажем, что [math]L\in DSPACE(g(n))\setminus DSPACE(f(n))[/math].
Так как [math]h(n)=o(g(n))[/math], то очевидно, что [math]L \in DSPACE(g(n))[/math]. Действительно, для проверки принадлежности программы [math]x[/math] языку достаточно запустить её с лимитом памяти [math]h(|x|)[/math] и проверить, что результат не равен 1. Тогда вся проверка будет выполнена с использованием не более [math]g(|x|)[/math] памяти в силу конструируемости функций [math]f[/math] и [math]g[/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 \Rightarrow c\cdot f(n)\lt h(n)[/math]. Будем считать, что [math]|p|\gt n_0[/math] (иначе добавим в программу пустые строки, искусственно увеличив её длину), тогда при вызове [math]p(p)[/math] потребуется не более [math]h(|p|)[/math] памяти. Выясним, принадлежит ли [math]p[/math] языку [math]L[/math]. Допустим, что [math]p\in L[/math], тогда [math]p(p)=1[/math], значит, [math]p\notin L[/math] по определению языка [math]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] |
| Определение: |
| Функция [math]f(x)[/math] называется конструируемой по времени, если можно вычислить [math]f(x)[/math] по [math]x[/math] за время не более [math]f(x)[/math]. |
| Теорема (о временной иерархии): |
Пусть даны две конструируемые по времени функции [math]f[/math] и [math]g[/math] такие, что [math]\lim \limits_{n\rightarrow\infty} \frac{Sim(f(n))}{g(n)}=0[/math], тогда [math]DTIME(f(n)) \varsubsetneq DTIME(g(n))[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Доказательство аналогично доказательству теоремы о емкостной иерархии. |
| [math]\triangleleft[/math] |
