Теорема Сэвича. Совпадение классов NPS и PS — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 16 промежуточных версий 8 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=Теорема Сэвича= | =Теорема Сэвича= | ||
Строка 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> памяти). | ||
Так как <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 \mathrm{NSPACE(f(n)) | + | Пусть <tex>L \in \mathrm{NSPACE}(f(n))</tex>. Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.<br> |
− | Рассмотрим функцию <tex>Reach(I, J, k)</tex>, вычисляющую возможность перехода из конфигурации <tex>I</tex> в конфигурацию <tex>J</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> | + | Рассмотрим машину Тьюринга <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>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
Теорема Сэвича
Теорема: |
Для любой справедливо: . То есть, если недетерминированная машина Тьюринга может решить проблему, используя памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем памяти. |
Доказательство: |
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию можно закодировать так: закодировать позицию и содержание рабочей ленты (займет памяти), позицию входной ленты (займет памяти). Так как , то размер конфигурации составит .Пусть Reach(I, J, k): if (k = 0) return (IJ) or (I = J) // запись (I J) означает возможность перехода МТ из конфигурации I в конфигурацию J за один шаг else for (Y) // перебор промежуточных конфигураций if Reach(I, Y, k-1) and Reach(Y, J, k-1) return true return false Эта функция имеет глубину рекурсии , на каждом уровне рекурсии использует памяти для хранения текущих конфигураций.Рассмотрим машину Тьюринга , распознающую язык . Эта машина может иметь конфигураций. Объясняется это следующим образом. Пусть имеет состояний и символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте . Головка на входной ленте может быть в одной из позиций и в одной из на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает .Рассмотрим функцию, которая по заданному слову проверяет его принадлежность языку : Check(x, L):
for (T) // перебор конфигураций, которые содержат допускающие состояния
if Reach(S, T,
)
return true
return false
Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции В итоге функция . И если слово не допускается за шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено. имеет глубину рекурсии , на каждом уровне рекурсии используется памяти. Тогда всего эта функция использует памяти. |
Следствие
Вывод
.
Известно, что
. Так что хотя бы одно из рассмотренных включений — строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения — строгие.См. также
Источники
- Michael Sipser. Introduction to the theory of computation.