76
правок
Изменения
Новая страница: «{{В разработке}} {{Теорема |about=О емкостной иерархии |id=space |statement=Пусть даны две конструируе...»
{{В разработке}}
{{Теорема
|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(g(n))\neq DSPACE(f(n))</tex>.
|proof=
Для доказательства воспользуемся диагональным методом. Рассмотрим функцию <tex>h(n)=\sqrt{f(n)g(n)}</tex>. Докажем, что <tex>L=\{x|x(x)\Bigr|_{s\leq O(h(|x|))}\neq 1\}\in DSPACE(g(n))\setminus DSPACE(f(n))</tex>. Иначе говоря, <tex>L</tex> — это язык программ, которые не возвращают 1 на собственном входе при условии ограничения на память <tex>O(h(|x|))</tex>.
Очевидно, что <tex>L \in DSPACE(g(n))</tex>. Предположим теперь, что <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~c\cdot f(n)<h(n)</tex>. Будем считать, что <tex>|p|>n_0</tex> (иначе добавим в программу пустые строки, искусственно увеличив её длину). Выясним, принадлежит ли <tex>p</tex> языку <tex>L</tex>. Допустим, что <tex>p\in L</tex>, тогда <tex>p(p)=1</tex>, причём ответ будет посчитан за время <tex>O(h(n))</tex>, значит, по определению <tex>p\notin L</tex>. Пусть теперь <tex>p\notin L</tex>. Но тогда по определению языка <tex>p(p)=1</tex>, значит, <tex>p\in L</tex>. Таким образом, язык <tex>L</tex> не может быть из <tex>DSPACE(f(n))</tex>, следовательно, язык из <tex>DSPACE(g(n))\setminus DSPACE(f(n))</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(g(n))\neq DSPACE(f(n))</tex>.
|proof=
Для доказательства воспользуемся диагональным методом. Рассмотрим функцию <tex>h(n)=\sqrt{f(n)g(n)}</tex>. Докажем, что <tex>L=\{x|x(x)\Bigr|_{s\leq O(h(|x|))}\neq 1\}\in DSPACE(g(n))\setminus DSPACE(f(n))</tex>. Иначе говоря, <tex>L</tex> — это язык программ, которые не возвращают 1 на собственном входе при условии ограничения на память <tex>O(h(|x|))</tex>.
Очевидно, что <tex>L \in DSPACE(g(n))</tex>. Предположим теперь, что <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~c\cdot f(n)<h(n)</tex>. Будем считать, что <tex>|p|>n_0</tex> (иначе добавим в программу пустые строки, искусственно увеличив её длину). Выясним, принадлежит ли <tex>p</tex> языку <tex>L</tex>. Допустим, что <tex>p\in L</tex>, тогда <tex>p(p)=1</tex>, причём ответ будет посчитан за время <tex>O(h(n))</tex>, значит, по определению <tex>p\notin L</tex>. Пусть теперь <tex>p\notin L</tex>. Но тогда по определению языка <tex>p(p)=1</tex>, значит, <tex>p\in L</tex>. Таким образом, язык <tex>L</tex> не может быть из <tex>DSPACE(f(n))</tex>, следовательно, язык из <tex>DSPACE(g(n))\setminus DSPACE(f(n))</tex> найден.}}
