Теорема Сэвича. Совпадение классов NPS и PS - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:42:04Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:26, 1 сентября 2022

2022-09-01T03:26:29Z

Kirillova в 17:40, 4 июня 2012

2012-06-04T17:40:52Z

Kirillova в 17:35, 4 июня 2012

2012-06-04T17:35:17Z

Kirillova: переименовал Класс PS. Теорема Сэвича. Совпадение классов NPS и PS в Теорема Сэвича. Совпадение классов NPS и PS

2012-06-04T17:33:04Z

переименовал Класс PS. Теорема Сэвича. Совпадение классов NPS и PS в Теорема Сэвича. Совпадение классов NPS и PS

Shevchen в 17:15, 4 июня 2012

2012-06-04T17:15:24Z

Leugenea: /* Определение */

2012-06-03T09:41:47Z

‎Определение

Leugenea: /* Теорема Сэвича */

2012-06-03T09:36:13Z

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

Kirelagin в 08:58, 3 июня 2012

2012-06-03T08:58:00Z

Igor buzhinsky: /* Теорема Сэвича */

2012-05-31T19:22:18Z

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

← Предыдущая		Версия 16:42, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	=Теорема Сэвича=		=Теорема Сэвича=

← Предыдущая		Версия 03:26, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	=Теорема Сэвича=		=Теорема Сэвича=

← Предыдущая		Версия 17:40, 4 июня 2012
Строка 47:		Строка 47:
	Известно, что <tex>\mathrm{L} \neq \mathrm{PS} </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.		Известно, что <tex>\mathrm{L} \neq \mathrm{PS} </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.

		+	= См. также =
		+	*[[Класс PS. Связь класса PS с другими классами теории сложности]]

	=Источники=		=Источники=

← Предыдущая		Версия 17:35, 4 июня 2012
Строка 1:		Строка 1:
−	~~=Класс PS=~~
−
−	~~== Определение ==~~
−	~~{{Определение~~
−	\|definition=<tex>\mathrm{PS}</tex> <tex>\mathrm{(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
−	~~<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.~~
−	}}
−
−	~~{{Определение~~
−	\|definition=<tex>\mathrm{NPS}</tex> <tex>\mathrm{(NPSPACE)}</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
−	~~<tex>\mathrm{NPS}=\bigcup\limits_{p(n) \in poly} \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>.
−	}}
−
	=Теорема Сэвича=		=Теорема Сэвича=

@@ Строка 53: / Строка 53: @@
 Рассмотрим машину Тьюринга <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):

← Предыдущая	Версия 17:33, 4 июня 2012
(нет различий)

@@ Строка 4: / Строка 4: @@
 {{Определение
 |definition=<tex>\mathrm{PS}</tex> <tex>\mathrm{(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
-<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{DSPACE}(p(n))</tex>.
+<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.
 }}
 {{Определение
 |definition=<tex>\mathrm{NPS}</tex> <tex>\mathrm{(NPSPACE)}</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
-<tex>\mathrm{NPS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{NSPACE}(p(n))</tex>.
+<tex>\mathrm{NPS}=\bigcup\limits_{p(n) \in poly} \mathrm{NSPACE}(p(n))</tex>.
 }}

@@ Строка 39: / Строка 39: @@
 Рассмотрим вспомогательную функцию <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)
-       '''return''' (I <tex>\vdash</tex> J) or (I = J);
+       '''return''' (I <tex>\vdash</tex> J) or (I = J)
      '''else'''
        '''for''' (Y) // перебор промежуточных конфигураций
          '''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> памяти для хранения текущих конфигураций.
@@ Строка 54: / Строка 55: @@
 Рассмотрим функцию, которая по заданному слову <tex>x</tex> проверяет его принадлежность к языку <tex>L</tex>:
-   '''Check''' (x, L)
+   '''Check'''(x, L):
      '''for''' (T) // перебор конфигураций, которые содержат допускающие состояния
        '''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> шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено.