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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 8 участников)
Строка 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>\mathrm{P}</tex> принадлежит <tex>\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>\mathrm{NP}</tex> принадлежит <tex>\mathrm{PS}</tex>.
 
}}
 
 
 
=Теорема Сэвича=
 
=Теорема Сэвича=
  
Строка 31: Строка 5:
 
Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>\mathrm{NSPACE}(f(n)) \subseteq \mathrm{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 (f(n)))+O(f(n))</tex> памяти), позицию входной ленты (займет <tex>O(\log n)</tex> памяти).
 
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log (f(n)))+O(f(n))</tex> памяти), позицию входной ленты (займет <tex>O(\log n)</tex> памяти).
Строка 37: Строка 11:
  
 
Пусть <tex>L \in \mathrm{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>2^{df(n)}</tex> шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено.  
Строка 72: Строка 47:
 
Известно, что <tex>\mathrm{L} \neq \mathrm{PS} </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.