Изменения

Перейти к: навигация, поиск

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

201 байт добавлено, 17:05, 4 июня 2012
Понижение формализма + диагональный метод
{{Определение
|id=space_foo
|definition=Функция <tex>f(x)</tex> называется '''конструируемой по памяти''', если можно вычислить <tex>f(x)</tex> по <tex>x</tex>, используя не более <tex>f(x)</tex> памяти.
}}
 
{{Теорема
|about=о емкостной иерархии
|id=space
|statement=Пусть даны две конструируемые по памяти функции <tex>f</tex> и <tex>g</tex> такие, что <tex>\lim \limits_{n\rightarrow\infty} \frac{f(n)}{g(n)}=0</tex>, тогда <tex>DSPACE(f(n)) \varsubsetneq DSPACE(g(n))</tex>.
|proof=
Понятно, что <tex>DSPACE(f(n)) \subseteq DSPACE(g(n))</tex>, поскольку программа, ограниченная по памяти функцией <tex>f</tex>, проходит ограничение <tex>g</tex>.<br />
Используя диагональный метод<ref>Суть данного метода заключается в рассмотрении среди набора функций <tex>\{f_r\}</tex> так называемых «диагональных элементов» вида <tex>f_r(r)</tex> и требовании неравенства их некоторой другой функции (в данном случае тождественно равной 1).</ref>, докажем, что включение строгое. Рассмотрим функцию <tex>h(n)=\sqrt{f(n)g(n)}</tex> и язык <tex>L=\{x\bigm|x(x)\Bigr|_{S\leq h(|x|)}\neq 1\}</tex>, где запись <tex>S\leq h(|x|)</tex> означает, что программа запускается с лимитом памяти <tex>h(|x|)</tex>. Иначе говоря, <tex>L</tex> — это язык программ, которые не допускают собственный код, используя не более <tex>h(|x|)</tex> памяти. Докажем, что <tex>L\in DSPACE(g(n))\setminus DSPACE(f(n))</tex>.<br/>Так как <tex>h(n)=o(g(n))</tex>, то понятно, что <tex>L \in DSPACE(g(n))</tex>. Действительно, для проверки принадлежности программы <tex>x</tex> языку достаточно запустить её с лимитом памяти <tex>h(|x|)</tex> и проверить, что результат не равен 1. Тогда вся проверка будет выполнена с использованием не более <tex>g(|x|)</tex> памяти в силу накладываемых ограничений.<ref>Вообще говоря, для корректного запуска с лимитом по памяти на функцию <tex>h</tex> дополнительно накладывается условие конструируемости функций по памяти, т. е. возможность вычислить значение функции по <tex>fx</tex> и , используя не более <tex>gh(x)</tex> и накладываемых ограничений на памятьпамяти, однако часто это условие опускается.</ref><br />
Предположим теперь, что <tex>L \in DSPACE(f(n))</tex>. Тогда существует программа <tex>p</tex>, распознающая язык <tex>L</tex> и использующая не более <tex>c \cdot f(n)</tex> памяти. Так как <tex>f(n)=o(h(n))</tex>, то <tex>\exists n_0: \forall n>n_0 \Rightarrow c\cdot f(n)<h(n)</tex>. Будем считать, что <tex>|p|>n_0</tex> (иначе добавим в программу пустые строки, искусственно увеличив её длину), тогда при вызове <tex>p(p)</tex> потребуется не более <tex>h(|p|)</tex> памяти. Выясним, принадлежит ли <tex>p</tex> языку <tex>L</tex>. Допустим, что <tex>p\in L</tex>, тогда <tex>p(p)=1</tex>, значит, <tex>p\notin L</tex> по определению языка <tex>L</tex>. Пусть теперь <tex>p\notin L</tex>. Но тогда <tex>p(p) \ne 1</tex>, следовательно, <tex>p\in L</tex>.
Таким образом, язык <tex>L</tex> не может быть из <tex>DSPACE(f(n))</tex>, следовательно, язык из <tex>DSPACE(g(n))\setminus DSPACE(f(n))</tex> найден.}}
 
{{Определение
|id=time_foo
|definition=Функция <tex>f(x)</tex> называется '''конструируемой по времени''', если можно вычислить <tex>f(x)</tex> по <tex>x</tex> за время не более <tex>f(x)</tex>.
}}
{{Теорема
|about=о временной иерархии
|id=time
|statement=Пусть даны две конструируемые по времени функции <tex>f</tex> и <tex>g</tex> такие, <span title="Здесь Sim(n) — время симуляции n шагов одной машины Тьюринга на другой машине" style="border-bottom: 1px dotted; cursor: help;">что</span> <tex>\lim \limits_{n\rightarrow\infty} \frac{Sim(f(n))}{g(n)}=0</tex>, тогда <tex>DTIME(f(n)) \varsubsetneq DTIME(g(n))</tex>.
|proof=Доказательство аналогично доказательству [[Теоремы о временной и емкостной иерархиях#space|теоремы о емкостной иерархии]].
}}
 
=== Замечания ===
<references />
[[Категория:Теория сложности]]
76
правок

Навигация