Теоремы о временной и ёмкостной иерархиях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
<!--Понятно, что <tex>DSPACE(f(n)) \subseteq DSPACE(g(n))</tex>, поскольку программа, ограниченная по памяти функцией <tex>f</tex>, проходит ограничение <tex>g</tex>.<br /> -->
 
<!--Понятно, что <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> иногда называют диагональными, поскольку для неотрицательных <tex>x</tex> находятся на диагонали таблицы функция — аргумент.
+
<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/><tex>
 
<br/><tex>
 
\begin{pmatrix}
 
\begin{pmatrix}

Версия 20:12, 4 июня 2012

Теорема (о емкостной иерархии):
Пусть даны две функции [math]f[/math] и [math]g[/math] такие, что [math]\lim \limits_{n\rightarrow\infty} \frac{f(n)}{g(n)}=0[/math], тогда [math]DSPACE(f(n)) \neq DSPACE(g(n))[/math].
Доказательство:
[math]\triangleright[/math]

Для доказательства воспользуемся диагональным методом. [1] Рассмотрим функцию [math]h(n)=\sqrt{f(n)g(n)}[/math] и язык [math]L=\{x\bigm|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] памяти в силу накладываемых ограничений.[2]
Предположим теперь, что [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) \ne 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[/math] и [math]g[/math] такие, что [math]\lim \limits_{n\rightarrow\infty} \frac{Sim(f(n))}{g(n)}=0[/math], тогда [math]DTIME(f(n)) \neq DTIME(g(n))[/math].
Доказательство:
[math]\triangleright[/math]
Доказательство аналогично доказательству теоремы о емкостной иерархии.
[math]\triangleleft[/math]

Замечания

  1. ↑ Суть данного метода для набора множеств [math]\{A_x\}[/math] заключается в построении нового множества [math]B[/math] по принципу: [math]x \in B \Leftrightarrow x \notin A_x[/math]. В этом случае [math]A_x \neq B[/math] для любого [math]x[/math]. Аналогичный прием можно применять для набора функций [math]\{f_i\}[/math] путем построения новой функции [math]f':f'(x) \neq f_x(x)[/math]. Элементы [math]f_x(x)[/math] иногда называют диагональными, поскольку находятся на диагонали таблицы функция — аргумент.
    [math] \begin{pmatrix} & 0 & 1 & \cdots \\ f_0 & \mathbf{f_0(0)} & f_0(1) & \cdots \\ f_1 & f_1(0) & \mathbf{f_1(1)} & \cdots \\ \vdots & \vdots & \vdots & \ddots \\ \end{pmatrix} [/math]
  2. ↑ Вообще говоря, для корректного запуска с лимитом по памяти на функцию [math]h[/math] дополнительно накладывается условие конструируемости по памяти, т. е. возможность вычислить значение функции по [math]x[/math], используя не более [math]h(x)[/math] памяти, однако часто это условие опускается.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теоремы_о_временной_и_ёмкостной_иерархиях&oldid=23827»