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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
м (Дмитрий Мурзин переименовал страницу Теорема о емкостной иерархии в Теорема о ёмкостной иерархии: Ёфикация)
 
(не показано 16 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
== Формулировка ==
 
== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется <tex>DSPACE(g(n)) \ne DSPACE(f(n))</tex>.
+
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется '''DSPACE'''(''g''(''n'')) &ne; '''DSPACE'''(''f''(''n'')).
  
 
== Доказательство ==
 
== Доказательство ==
Зафиксируем <tex>f</tex> и <tex>g</tex>.
+
Зафиксируем функции <tex>f</tex> и <tex>g</tex>.
  
Рассмотрим язык <tex>L = \{ \langle m,x\rangle \mid m(\langle m,x\randle)</tex> не допускает, используя не более <tex> f(|\langle m,x\rangle|)</tex> памяти <tex>\}</tex> .
+
Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )</tex> не допускает, используя не более <tex> f(|\langle m,x\rangle|)</tex> памяти <tex>\}</tex> и докажем, что <tex>L \notin DSPACE(f)</tex> и <tex>L \in DSPACE(g)</tex>.
  
Пусть <tex>L \in DSPACE(f)</tex>, тогда для него есть машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0)=L</tex>.
+
Допустим, что <tex>L \in DSPACE(f)</tex>, тогда существует детерминированная машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0)=L</tex>.
  
Рассмотрим <tex>m_0(\langle m_0,x\rangle)</tex>.  
+
Рассмотрим выход машины <tex>m_0</tex> на входе <tex>\langle m_0,x\rangle</tex>.
  
Пусть <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>. Тогда <tex>\langle m_0,x\rangle \in L</tex>, но в  <tex>L</tex> по определению не может быть пары <tex>\langle m,x\rangle</tex>, которую допускает <tex>m</tex>. Таким образом, получаем противоречие.
+
Пусть <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>. Тогда <tex>\langle m_0,x\rangle \in L</tex>, но в  <tex>L</tex> по определению не может быть пары <tex>\langle m,x\rangle</tex>, которую допускает <tex>m</tex>. Таким образом, <tex>m_0</tex> не может допускать <tex>\langle m_0,x\rangle</tex>.
  
Если <tex>m_0</tex> не допускает <tex><m_0,x></tex>, то <tex>\langle m_0,x\rangle</tex> не принадлежит языку <tex>L</tex>. Это значит, что либо <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>, либо не допускает, используя памяти больше <tex>f(|<m_0,x>|)</tex>. Но <tex>m_0</tex> выбрана таким образом, что на любом входе <tex>x</tex> она использует не более <tex>f(|x|)</tex> памяти. Получаем противоречие.  
+
Если <tex>m_0</tex> не допускает <tex>\langle m_0,x\rangle</tex>, то <tex>\langle m_0,x\rangle</tex> не принадлежит языку <tex>L</tex>. Из определения это значит, что либо <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>, либо не допускает, используя памяти больше <tex>f(|\langle m_0,x\rangle|)</tex>. Но <tex>m_0</tex> выбрана таким образом, что на любом входе <tex>x</tex> она использует не более <tex>f(|x|)</tex> памяти. Получаем противоречие.
  
 
Следовательно, такой машины не существует. Таким образом, <tex>L \notin DSPACE(f)</tex>.
 
Следовательно, такой машины не существует. Таким образом, <tex>L \notin DSPACE(f)</tex>.
  
<math>L \in DSPACE(g)</math>, так как можно проэмулировать машину Тьюринга <math>m_1</math> такую, что <math>L(m_1)=L</math>. Для каждой пары <math><m_3,x> \in L</math> рассмотрим <math>m_3(<m_3,x>)\,\!</math>. Если <math>m_3</math> завершила работу и не допустила, то <math>m_1</math> допускает <math><m_3,x></math>. В другом случае не допускает. Так как любая такая машина использует памяти не более <math>f(|<m_3,x>|)</math>, а <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, <math>m_1</math> будет использовать памяти не более <math>g(|<m_3,x>|)</math>.
+
<tex>L \in DSPACE(g)</tex>, так как языку <tex>L</tex> можно сопоставить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex> и такую, что на любом входе <tex>\langle m_1,x\rangle \in L</tex> <tex>m_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(|\langle m_1,x\rangle|)</tex> памяти, и не допустила, то <tex>m_0</tex> допускает <tex>\langle m_1,x\rangle</tex>. В другом случае не допускает. Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>. По условию теоремы <tex>\lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, поэтому начиная с некоторого <tex>n</tex>, <tex>m_1</tex> будет использовать памяти не более <tex>g(|\langle m_1,x\rangle|)</tex>.
  
 
+
Таким образом получили, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>, что и требовалось доказать.
Получается, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex> и <tex>L \neq \empty</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>
 
 
 
Теорема доказана.
 

Текущая версия на 23:51, 31 января 2019

Формулировка[править]

Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций [math]f[/math] и [math]g[/math] таких, что [math] \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0[/math], выполняется DSPACE(g(n)) ≠ DSPACE(f(n)).

Доказательство[править]

Зафиксируем функции [math]f[/math] и [math]g[/math].

Рассмотрим язык [math]L = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )[/math] не допускает, используя не более [math] f(|\langle m,x\rangle|)[/math] памяти [math]\}[/math] и докажем, что [math]L \notin DSPACE(f)[/math] и [math]L \in DSPACE(g)[/math].

Допустим, что [math]L \in DSPACE(f)[/math], тогда существует детерминированная машина Тьюринга [math]m_0[/math] такая, что [math]L(m_0)=L[/math].

Рассмотрим выход машины [math]m_0[/math] на входе [math]\langle m_0,x\rangle[/math].

Пусть [math]m_0[/math] допускает [math]\langle m_0,x\rangle[/math]. Тогда [math]\langle m_0,x\rangle \in L[/math], но в [math]L[/math] по определению не может быть пары [math]\langle m,x\rangle[/math], которую допускает [math]m[/math]. Таким образом, [math]m_0[/math] не может допускать [math]\langle m_0,x\rangle[/math].

Если [math]m_0[/math] не допускает [math]\langle m_0,x\rangle[/math], то [math]\langle m_0,x\rangle[/math] не принадлежит языку [math]L[/math]. Из определения это значит, что либо [math]m_0[/math] допускает [math]\langle m_0,x\rangle[/math], либо не допускает, используя памяти больше [math]f(|\langle m_0,x\rangle|)[/math]. Но [math]m_0[/math] выбрана таким образом, что на любом входе [math]x[/math] она использует не более [math]f(|x|)[/math] памяти. Получаем противоречие.

Следовательно, такой машины не существует. Таким образом, [math]L \notin DSPACE(f)[/math].

[math]L \in DSPACE(g)[/math], так как языку [math]L[/math] можно сопоставить машину Тьюринга [math]m_0[/math], распознающую [math]L[/math] и такую, что на любом входе [math]\langle m_1,x\rangle \in L[/math] [math]m_0[/math] будет работать аналогично [math]m_1[/math]. Если [math]m_1[/math] завершила работу, используя не более [math]f(|\langle m_1,x\rangle|)[/math] памяти, и не допустила, то [math]m_0[/math] допускает [math]\langle m_1,x\rangle[/math]. В другом случае не допускает. Любая такая машина использует памяти не более [math]f(|\langle m_1,x\rangle|)[/math]. По условию теоремы [math]\lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0[/math], поэтому начиная с некоторого [math]n[/math], [math]m_1[/math] будет использовать памяти не более [math]g(|\langle m_1,x\rangle|)[/math].

Таким образом получили, что [math]L \in DSPACE(g(n)) \setminus DSPACE(f(n))[/math]. Следовательно, [math]DSPACE(g(n)) \neq DSPACE(f(n))[/math], что и требовалось доказать.