Теорема Сэвича. Совпадение классов NPS и PS — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 21 промежуточная версия 8 участников)
Строка 1: Строка 1:
=Класс ''PS''=
 
 
== Определение ==
 
{{Определение
 
|definition='''Класс''' <tex>PS(PSPACE)</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера.
 
<tex>PS=\bigcup\limits_{p(n)-poly} DSPACE(p(n))</tex>
 
}}
 
 
{{Определение
 
|definition='''Класс''' <tex>NPS(NPSPACE)</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера.
 
<tex>NPS=\bigcup\limits_{p(n)-poly} NSPACE(p(n))</tex>
 
}}
 
 
== Связь класса ''PS'' с другими классами теории сложности ==
 
{{Теорема
 
|statement =
 
<tex>P \subseteq PS</tex>.
 
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>P</tex>. Так как <tex>L \in P</tex>, то существует машина Тьюринга <tex>m</tex>, распознающая <tex>L</tex> за полиномиальное время. Это значит, что <tex>m</tex> не успеет использовать память, размер которой превосходит полиномиальное значение. Тогда любой язык из <tex>P</tex> принадлежит <tex>PS</tex>.
 
}}
 
 
{{Теорема
 
|statement =
 
<tex>NP \subseteq PS</tex>.
 
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>NP</tex>. Так как <tex>L \in NP</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует сертификат <tex>y</tex> полиномиальной длины, такой, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины, а для этого необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>.
 
}}
 
 
{{Теорема
 
|statement =
 
<tex>L \subseteq P</tex>.
 
|proof = Машина Тьюринга, распознающая язык из <tex>L</tex>, используя не более <tex>O(\log n)</tex> памяти, работает не более чем <tex>2^{O(\log n)} = poly(n)</tex> времени.
 
}}
 
 
=== Вывод===
 
<tex>L \subseteq P \subseteq NP \subseteq PS</tex>.
 
 
Известно, что <tex>L \neq PS </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.
 
 
 
=Теорема Сэвича=
 
=Теорема Сэвича=
  
 
{{Теорема
 
{{Теорема
 
|statement =
 
|statement =
Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>NSPACE(f(n)) \subseteq DSPACE(f(n)^2)</tex>. <br>
+
Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)</tex>. <br>
  
То есть, если недетерминированная машина Тьюринга может решить проблему используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти.
+
То есть, если недетерминированная машина Тьюринга может решить проблему, используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти.
 
|proof =  
 
|proof =  
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log n)+O(f(n))</tex> памяти), содержание входной ленты (займет <tex>O(n)</tex> памяти).
+
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log (f(n)))+O(f(n))</tex> памяти), позицию входной ленты (займет <tex>O(\log n)</tex> памяти).
 
Так как <tex>f(n) \ge \log n </tex>, то размер конфигурации составит <tex>O(f(n))</tex>.
 
Так как <tex>f(n) \ge \log n </tex>, то размер конфигурации составит <tex>O(f(n))</tex>.
  
Пусть <tex>L \in NSPACE(f(n))</tex>. Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.<br>
+
Пусть <tex>L \in \mathrm{NSPACE}(f(n))</tex>. Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.<br>
Рассмотрим функцию <tex>Reach(I, J, k)</tex>, вычисляющую возможность перехода из конфигурации <tex>I</tex> в конфигурацию <tex>J</tex> за <tex>2^k</tex> переходов:
+
Рассмотрим вспомогательную функцию <tex>Reach(I, J, k)</tex>, вычисляющую возможность перехода из конфигурации <tex>I</tex> в конфигурацию <tex>J</tex> за не более, чем <tex>2^k</tex> переходов:
  
   '''Reach''' (I, J, k)
+
   '''Reach'''(I, J, k):
 
     '''if''' (k = 0)
 
     '''if''' (k = 0)
       '''return''' (I <tex>\vdash</tex> J) or (I = J);
+
       '''return''' (I <tex>\vdash</tex> J) or (I = J)
 +
    // запись (I <tex>\vdash</tex> J) означает возможность перехода МТ из конфигурации I в конфигурацию J за один шаг
 
     '''else'''
 
     '''else'''
 
       '''for''' (Y) // перебор промежуточных конфигураций
 
       '''for''' (Y) // перебор промежуточных конфигураций
 
         '''if''' Reach(I, Y, k-1) and Reach(Y, J, k-1)
 
         '''if''' Reach(I, Y, k-1) and Reach(Y, J, k-1)
           '''return''' true;
+
           '''return''' true
     '''return''' false;
+
     '''return''' false
  
Эта функция имеет глубину рекурсии <tex>O(k)</tex>, на каждом уровне рекурсии использует <tex>O(f(n))</tex> памяти для хранения текущих конфигураций. Тогда всего функция использует <tex>O(kf(n))</tex> памяти.
+
Эта функция имеет глубину рекурсии <tex>O(k)</tex>, на каждом уровне рекурсии использует <tex>O(f(n))</tex> памяти для хранения текущих конфигураций.
  
Рассмотрим машину Тьюринга <tex>M</tex>, распознающую язык <tex>L</tex>. Эта машина может иметь <tex>2^{df(n)}</tex> конфигураций. Объясняется это следующим образом. Пусть <tex>M</tex> имеет <tex>c</tex> состояний и <tex>g</tex> символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте <tex>g^{f(n)}</tex>. Головка на входной ленте может быть в одной из n позиций и в одной из <tex>f(n)</tex> на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает <tex>cnf(n)g^{f(n)}=2^{\log c + \log n + \log (f(n)) + f(n) \log g}=2^{O(f(n))}</tex>.
+
Рассмотрим машину Тьюринга <tex>m</tex>, распознающую язык <tex>L</tex>. Эта машина может иметь <tex>2^{df(n)}</tex> конфигураций. Объясняется это следующим образом. Пусть <tex>m</tex> имеет <tex>c</tex> состояний и <tex>g</tex> символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте <tex>g^{f(n)}</tex>. Головка на входной ленте может быть в одной из <tex>n</tex> позиций и в одной из <tex>f(n)</tex> на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает <tex>cnf(n)g^{f(n)}=2^{\log c + \log n + \log (f(n)) + f(n) \log g}=2^{O(f(n))}</tex>.
  
Рассмотрим функцию, которая по заданному слову <tex>x</tex> проверяет его принадлежность к языку <tex>L</tex>:
+
Рассмотрим функцию, которая по заданному слову <tex>x</tex> проверяет его принадлежность языку <tex>L</tex>:
  
   '''Check''' (x, L)
+
   '''Check'''(x, L):
 
     '''for''' (T) // перебор конфигураций, которые содержат допускающие состояния
 
     '''for''' (T) // перебор конфигураций, которые содержат допускающие состояния
 
       '''if''' Reach(S, T, <tex>\log \left(2^{df(n)}\right)</tex>)
 
       '''if''' Reach(S, T, <tex>\log \left(2^{df(n)}\right)</tex>)
         '''return''' true;
+
         '''return''' true
     '''return''' false;
+
     '''return''' false
  
 +
Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции <tex>Reach</tex>. И если слово не допускается за <tex>2^{df(n)}</tex> шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено.
 
В итоге функция <tex>Reach</tex> имеет глубину рекурсии <tex>\log{2}^{df(n)}=O(f(n))</tex>, на каждом уровне рекурсии используется <tex>O(f(n))</tex> памяти. Тогда всего эта функция использует <tex>O(f(n)^2)</tex> памяти.
 
В итоге функция <tex>Reach</tex> имеет глубину рекурсии <tex>\log{2}^{df(n)}=O(f(n))</tex>, на каждом уровне рекурсии используется <tex>O(f(n))</tex> памяти. Тогда всего эта функция использует <tex>O(f(n)^2)</tex> памяти.
 
}}
 
}}
  
 
==Следствие==
 
==Следствие==
<tex>PS=NPS</tex>
+
<tex>\mathrm{PS}=\mathrm{NPS}</tex>
 +
 
 +
=Вывод=
 +
<tex>\mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PS} = \mathrm{NPS}</tex>.
 +
 
 +
Известно, что <tex>\mathrm{L} \neq \mathrm{PS} </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.
 +
 
 +
= См. также =
 +
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
  
 
=Источники=
 
=Источники=
 
* Michael Sipser. Introduction to the theory of computation.
 
* Michael Sipser. Introduction to the theory of computation.
 +
 +
[[Категория: Теория сложности]]

Текущая версия на 19:42, 4 сентября 2022

Теорема Сэвича

Теорема:
Для любой [math]f(n) \ge \log n [/math] справедливо: [math]\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)[/math].
То есть, если недетерминированная машина Тьюринга может решить проблему, используя [math]f(n)[/math] памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем [math]f(n)^2[/math] памяти.
Доказательство:
[math]\triangleright[/math]

Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию [math]I[/math] можно закодировать так: закодировать позицию и содержание рабочей ленты (займет [math]O(\log (f(n)))+O(f(n))[/math] памяти), позицию входной ленты (займет [math]O(\log n)[/math] памяти). Так как [math]f(n) \ge \log n [/math], то размер конфигурации составит [math]O(f(n))[/math].

Пусть [math]L \in \mathrm{NSPACE}(f(n))[/math]. Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.
Рассмотрим вспомогательную функцию [math]Reach(I, J, k)[/math], вычисляющую возможность перехода из конфигурации [math]I[/math] в конфигурацию [math]J[/math] за не более, чем [math]2^k[/math] переходов:

 Reach(I, J, k):
   if (k = 0)
     return (I [math]\vdash[/math] J) or (I = J)
   // запись (I [math]\vdash[/math] J) означает возможность перехода МТ из конфигурации I в конфигурацию J за один шаг
   else
     for (Y) // перебор промежуточных конфигураций
       if Reach(I, Y, k-1) and Reach(Y, J, k-1)
         return true
   return false

Эта функция имеет глубину рекурсии [math]O(k)[/math], на каждом уровне рекурсии использует [math]O(f(n))[/math] памяти для хранения текущих конфигураций.

Рассмотрим машину Тьюринга [math]m[/math], распознающую язык [math]L[/math]. Эта машина может иметь [math]2^{df(n)}[/math] конфигураций. Объясняется это следующим образом. Пусть [math]m[/math] имеет [math]c[/math] состояний и [math]g[/math] символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте [math]g^{f(n)}[/math]. Головка на входной ленте может быть в одной из [math]n[/math] позиций и в одной из [math]f(n)[/math] на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает [math]cnf(n)g^{f(n)}=2^{\log c + \log n + \log (f(n)) + f(n) \log g}=2^{O(f(n))}[/math].

Рассмотрим функцию, которая по заданному слову [math]x[/math] проверяет его принадлежность языку [math]L[/math]:

 Check(x, L):
   for (T) // перебор конфигураций, которые содержат допускающие состояния
     if Reach(S, T, [math]\log \left(2^{df(n)}\right)[/math])
       return true
   return false

Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции [math]Reach[/math]. И если слово не допускается за [math]2^{df(n)}[/math] шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено.

В итоге функция [math]Reach[/math] имеет глубину рекурсии [math]\log{2}^{df(n)}=O(f(n))[/math], на каждом уровне рекурсии используется [math]O(f(n))[/math] памяти. Тогда всего эта функция использует [math]O(f(n)^2)[/math] памяти.
[math]\triangleleft[/math]

Следствие

[math]\mathrm{PS}=\mathrm{NPS}[/math]

Вывод

[math]\mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PS} = \mathrm{NPS}[/math].

Известно, что [math]\mathrm{L} \neq \mathrm{PS} [/math]. Так что хотя бы одно из рассмотренных включений — строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения — строгие.

См. также

Источники

  • Michael Sipser. Introduction to the theory of computation.