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

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 20 промежуточных версий 5 участников)
Строка 1: Строка 1:
−
{{Определение
 
−
|id=space_foo
 
−
|definition=Функция <tex>f(x)</tex> называется '''конструируемой по памяти''', если можно вычислить <tex>f(x)</tex> по <tex>x</tex>, используя не более <tex>f(x)</tex> памяти.
 
−
}}
 
−
 
 
{{Теорема
 
{{Теорема
 
|about=о емкостной иерархии
 
|about=о емкостной иерархии
 
|id=space
 
|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>.
+
|statement=Пусть даны две функции <tex>f</tex> и <tex>g</tex> такие, что <tex>\lim \limits_{n\rightarrow\infty} \frac{f(n)}{g(n)}=0</tex>, тогда <tex>DSPACE(f(n)) \neq DSPACE(g(n))</tex><ref>Строго говоря, теорема верна только для конструируемых по памяти функций <tex>f</tex> и <tex>g</tex>. Функция <tex>f</tex> называется конструируемой по памяти, если можно вычислить ее значение, используя не более <tex>f(x)</tex> памяти (см. [1]).</ref>.
 
|proof=
 
|proof=
−
Для доказательства воспользуемся диагональным методом. Рассмотрим функцию <tex>h(n)=\sqrt{f(n)g(n)}</tex> и язык <tex>L=\{x|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>.  
+
<!--Понятно, что <tex>DSPACE(f(n)) \subseteq DSPACE(g(n))</tex>, поскольку программа, ограниченная по памяти функцией <tex>f</tex>, проходит ограничение <tex>g</tex>.<br /> -->
−
Т. к. <tex>h(n)=o(g(n))</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(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)=1</tex>, следовательно, <tex>p\in L</tex>. Таким образом, язык <tex>L</tex> не может быть из <tex>DSPACE(f(n))</tex>, следовательно, язык из <tex>DSPACE(g(n))\setminus DSPACE(f(n))</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/>
−
|id=time_foo
+
{| class="wikitable" align="centre"
−
|definition=Функция <tex>f(x)</tex> называется '''конструируемой по времени''', если можно вычислить <tex>f(x)</tex> по <tex>x</tex> за время не более <tex>f(x)</tex>.
+
|-
−
}}
+
| ||<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|_{S\leq h(|x|)}\neq 1\}</tex>, где запись <tex>S\leq h(|x|)</tex> означает, что программа запускается с лимитом памяти <tex>h(|x|)</tex>. Иначе говоря, <tex>L</tex> — это язык программ, которые не допускают собственный код, используя не более <tex>h(|x|)</tex> памяти.<br/>
 +
Докажем, что <tex>L\in DSPACE(g(n))\setminus DSPACE(f(n))</tex>.<br/>
 +
* <tex>L \in DSPACE(g(n))</tex>. Действительно, для проверки принадлежности программы <tex>x</tex> языку достаточно запустить её с лимитом памяти <tex>h(|x|)</tex> и проверить, что результат не равен 1. Тогда вся проверка будет выполнена с использованием не более <tex>g(|x|)</tex> памяти в силу накладываемых ограничений.<br />
 +
* <tex>L \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> найден.}}
  
 
{{Теорема
 
{{Теорема
 
|about=о временной иерархии
 
|about=о временной иерархии
 
|id=time
 
|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(g(n))\neq DTIME(f(n))</tex>.  
+
|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(f(n)) \neq DTIME(g(n))</tex>.  
−
|proof=Доказательство аналогично доказательству [[Теоремы о временной и емкостной иерархиях#space|теоремы о емкостной иерархии]].
+
|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'''
  
 
[[Категория:Теория сложности]]
 
[[Категория:Теория сложности]]

Версия 23:52, 31 января 2019

Теорема (о емкостной иерархии):
Пусть даны две функции [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][1].
Доказательство:
[math]\triangleright[/math]

Для доказательства воспользуемся диагональным методом. [2]
Рассмотрим функцию [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]L \in DSPACE(g(n))[/math]. Действительно, для проверки принадлежности программы [math]x[/math] языку достаточно запустить её с лимитом памяти [math]h(|x|)[/math] и проверить, что результат не равен 1. Тогда вся проверка будет выполнена с использованием не более [math]g(|x|)[/math] памяти в силу накладываемых ограничений.
  • [math]L \notin 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]Sim(n)[/math] — время симуляции [math]n[/math] шагов одной машины Тьюринга на другой машине. Тогда [math]DTIME(f(n)) \neq DTIME(g(n))[/math].
Доказательство:
[math]\triangleright[/math]

Доказательство аналогично доказательству теоремы о емкостной иерархии. При этом в отличие от памяти, время работы машины Тьюринга меньше, чем время ее симуляции на другой машине, из-за чего на соотношение [math]f[/math] и [math]g[/math] поставлено более сильное условие. Положим [math]h(n)=Sim^{-1}(g(n))[/math], где [math]Sim^{-1}[/math] — обратная к времени симуляции функция, [math]L=\{x\bigm|x(x)\Bigr|_{T\leq h(|x|)}\neq 1\}[/math]. Тогда:

  • [math]L \in DTIME(g(n))[/math], поскольку [math]Sim(h(n))=g(n)[/math], то есть запуск с ограничением [math]T \leq h(|x|)[/math] осуществляется за [math]O(g(n))[/math] времени;
  • [math]L \notin DTIME(f(n))[/math] (доказывается аналогично соответствующему пункту предыдущей теоремы с учетом соотношения [math]f(n)=o(h(n))[/math]).
[math]\triangleleft[/math]

Примечания

  1. ↑ Строго говоря, теорема верна только для конструируемых по памяти функций [math]f[/math] и [math]g[/math]. Функция [math]f[/math] называется конструируемой по памяти, если можно вычислить ее значение, используя не более [math]f(x)[/math] памяти (см. [1]).
  2. ↑ Суть данного метода для набора множеств [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]0[/math] [math]1[/math] [math]\cdots[/math]
    [math]f_0[/math] [math]\mathbf{f_0(0)}[/math] [math]f_0(1)[/math] [math]\cdots[/math]
    [math]f_1[/math] [math]f_1(0)[/math] [math]\mathbf{f_1(1)}[/math] [math]\cdots[/math]
    [math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\ddots[/math]

Литература

  1. Sanjeev Arora, Boaz Barak — Computational Complexity: A Modern Approach — С. 69, 82. — 579 с. — ISBN 9780521424264
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теоремы_о_временной_и_ёмкостной_иерархиях&oldid=69812»