Изменения

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

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

2854 байта добавлено, 19:21, 4 сентября 2022
м
rollbackEdits.php mass rollback
{{В разработке}}
 
{{Определение
|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(gf(n))\neq DSPACE(fg(n))</tex><ref>Строго говоря, теорема верна только для конструируемых по памяти функций <tex>f</tex> и <tex>g</tex>. Функция <tex>f</tex> называется конструируемой по памяти, если можно вычислить ее значение, используя не более <tex>f(x)</tex> памяти (см. [1]).</ref>.
|proof=
<!--Понятно, что <tex>DSPACE(f(n)) \subseteq DSPACE(g(n))</tex>, поскольку программа, ограниченная по памяти функцией <tex>f</tex>, проходит ограничение <tex>g</tex>.<br /> -->Для доказательства воспользуемся диагональным методом. <ref>Суть данного метода для набора множеств <tex>\{A_x\}</tex> заключается в построении нового множества <tex>B</tex> по принципу: <tex>x \in B \Leftrightarrow x \notin A_x</tex> (в таком случае <tex>A_x \neq B</tex> для любого <tex>x</tex>). Аналогичный прием можно применять для набора функций <tex>\{f_i\}</tex> путем построения новой функции <tex>f':f'(x) \neq f_x(x)</tex>. Элементы <tex>f_x(x)</tex> иногда называют диагональными, поскольку находятся на диагонали таблицы «функция — аргумент».<br/>{| class="wikitable" align="centre"|-| ||<tex>0</tex>||<tex>1</tex>||<tex>\cdots</tex>|-|<tex>f_0</tex>||<tex>\mathbf{f_0(0)}</tex>||<tex>f_0(1)</tex>||<tex>\cdots</tex>|-|<tex>f_1</tex>||<tex>f_1(0)</tex>||<tex>\mathbf{f_1(1)}</tex>||<tex>\cdots</tex>|-|<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\ddots</tex>|-|}</ref><br/>Рассмотрим функцию <tex>h(n)=\sqrt{f(n)g(n)}</tex> и язык <tex>L=\{x\bigm|x(x)\Bigr|_{sS\leq h(|x|)}\neq 1\}</tex>, где запись <tex>sS\leq h(|x|)</tex> — ограничение на памятьозначает, в случае достижения которого выполнение программы прерываетсячто программа запускается с лимитом памяти <tex>h(|x|)</tex>. Иначе говоря, <tex>L</tex> — это язык программ, которыене допускают собственный код, если на вход подать саму программу, используя не возвращают 1 при условии ограничения на память более <tex>h(|x|)</tex>памяти. <br/>Докажем, что <tex>L\in DSPACE(g(n))\setminus DSPACE(f(n))</tex>. <br/>* <span title="Т. к. h(n)=otex>L \in DSPACE(g(n))" style="border-bottom: 1px dotted; cursor: help;"</tex>. Действительно, для проверки принадлежности программы <tex>x</tex> языку достаточно запустить её с лимитом памяти <tex>Очевидноh(|x|)</spantex>и проверить, что результат не равен 1. Тогда вся проверка будет выполнена с использованием не более <tex>L \in DSPACE(g(n)|x|)</tex>памяти в силу накладываемых ограничений. Предположим теперь, что <br />* <tex>L \in notin 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> такие, что <tex>\lim \limits_{n\rightarrow\infty} \frac{Sim(f(n))}{g(n)}=0</tex>, тогда где <tex>Sim(n)</tex> — время симуляции <tex>n</tex> шагов одной машины Тьюринга на другой машине. Тогда <tex>DTIME(gf(n))\neq DTIME(fg(n))</tex>.|proof=Доказательство аналогично доказательству [[Теоремы о временной и емкостной иерархиях#space|теоремы о емкостной иерархии]]. При этом в отличие от памяти, время работы машины Тьюринга меньше, чем время ее симуляции на другой машине, из-за чего на соотношение <tex>f</tex> и <tex>g</tex> поставлено более сильное условие.Положим <tex>h(n)=Sim^{-1}(g(n))</tex>, где <tex>Sim^{-1}</tex> — обратная к времени симуляции функция, <tex>L=\{x\bigm|x(x)\Bigr|_{T\leq h(|x|)}\neq 1\}</tex>. Тогда:* <tex>L \in DTIME(g(n))</tex>, поскольку <tex>Sim(h(n))=g(n)</tex>, то есть запуск с ограничением <tex>T \leq h(|x|)</tex> осуществляется за <tex>O(g(n))</tex> времени;* <tex>L \notin DTIME(f(n))</tex> (доказывается аналогично соответствующему пункту предыдущей теоремы с учетом соотношения <tex>f(n)=o(h(n))</tex>).
}}
 
== Примечания ==
<references />
 
== Литература ==
# ''Sanjeev Arora, Boaz Barak'' — '''Computational Complexity: A Modern Approach''' — С. 69, 82. — 579 с. — '''ISBN 9780521424264'''
 
[[Категория:Теория сложности]]
1632
правки

Навигация