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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Сэвича)
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 6 участников)
Строка 1: Строка 1:
=Класс PS=
 
 
== Определение ==
 
{{Определение
 
|definition=<tex>\mathrm{PS(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
 
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{DSPACE}(p(n)) </tex>
 
}}
 
 
{{Определение
 
|definition=<tex>\mathrm{NPS(NPSPACE)}</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
 
<tex>\mathrm{NPS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{NSPACE}(p(n))</tex>
 
}}
 
 
== Связь класса PS с другими классами теории сложности ==
 
{{Теорема
 
|statement =
 
<tex>\mathrm{P} \subseteq \mathrm{PS}</tex>.
 
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{P}</tex>. Так как <tex>L \in \mathrm{P}</tex>, то существует машина Тьюринга <tex>m</tex>, распознающая <tex>L</tex> за полиномиальное время. Это значит, что <tex>m</tex> не сможет использовать более, чем полиномиальное количество памяти, следовательно <tex> L \in \mathrm{PS}</tex>.
 
}}
 
 
{{Теорема
 
|statement =
 
<tex>\mathrm{NP} \subseteq \mathrm{PS}</tex>.
 
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{NP}</tex>. Так как <tex>L \in \mathrm{NP}</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует такой сертификат <tex>y</tex> полиномиальной длины, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что <tex>L \in \mathrm{PS}</tex>.
 
}}
 
 
 
=Теорема Сэвича=
 
=Теорема Сэвича=
  
Строка 39: Строка 13:
 
Рассмотрим вспомогательную функцию <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(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>2^{df(n)}</tex> шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено.  
Строка 72: Строка 47:
 
Известно, что <tex>\mathrm{L} \neq \mathrm{PS} </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.
 
Известно, что <tex>\mathrm{L} \neq \mathrm{PS} </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.
  
 +
= См. также =
 +
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
  
 
=Источники=
 
=Источники=

Текущая версия на 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.