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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
{{В разработке}}
 
 
 
{{Определение
 
{{Определение
 
|id=space_foo
 
|id=space_foo
|definition=Функция <tex>f(x)</tex> называется '''конструируемой по памяти''', если можно вычислить <tex>f(x)</tex> по <tex>x</tex>, используя памяти не более <tex>f(x)</tex>.
+
|definition=Функция <tex>f(x)</tex> называется '''конструируемой по памяти''', если можно вычислить <tex>f(x)</tex> по <tex>x</tex>, используя не более <tex>f(x)</tex> памяти.
 
}}
 
}}
  
Строка 11: Строка 9:
 
|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(g(n))\neq DSPACE(f(n))</tex>.
 
|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</tex> — ограничение на память, в случае достижения которого выполнение программы прерывается. Иначе говоря, <tex>L</tex> — это язык программ, которые, если на вход подать саму программу, не возвращают 1 при условии ограничения на память <tex>h(|x|)</tex>. Докажем, что <tex>L\in DSPACE(g(n))\setminus DSPACE(f(n))</tex>.  
+
Для доказательства воспользуемся диагональным методом. Рассмотрим функцию <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>.  
<span title="Т. к. h(n)=o(g(n))" style="border-bottom: 1px dotted; cursor: help;">Очевидно</span>, что <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> найден.}}
+
Т. к. <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> найден.}}
  
 
{{Определение
 
{{Определение
Строка 22: Строка 20:
 
|about=о временной иерархии
 
|about=о временной иерархии
 
|id=time
 
|id=time
|statement=Пусть даны две конструируемые по времени функции <tex>f</tex> и <tex>g</tex> такие, что <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> такие, <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>.  
 
|proof=Доказательство аналогично доказательству [[Теоремы о временной и емкостной иерархиях#space|теоремы о емкостной иерархии]].
 
|proof=Доказательство аналогично доказательству [[Теоремы о временной и емкостной иерархиях#space|теоремы о емкостной иерархии]].
 
}}
 
}}
 +
 +
[[Категория:Теория сложности]]

Версия 16:20, 15 апреля 2012

Определение:
Функция [math]f(x)[/math] называется конструируемой по памяти, если можно вычислить [math]f(x)[/math] по [math]x[/math], используя не более [math]f(x)[/math] памяти.


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

Для доказательства воспользуемся диагональным методом. Рассмотрим функцию [math]h(n)=\sqrt{f(n)g(n)}[/math] и язык [math]L=\{x|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]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~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)=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(x)[/math] называется конструируемой по времени, если можно вычислить [math]f(x)[/math] по [math]x[/math] за время не более [math]f(x)[/math].


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