S2P (сложность)

В сложности вычислений теории S ^П
₂ — класс сложности , промежуточный между первым и вторым уровнями полиномиальной иерархии . Язык $L$ находится в ${\mathsf {S}}_{2}^{P}$ если существует предикат P с полиномиальным временем такой, что

Если $x\in L$ , то существует y такой, что для всех z , $P(x,y,z)=1$ ,
Если $x\notin L$ , то существует z такой, что для y всех $P(x,y,z)=0$ ,

где размер y и z должен быть полиномом x .

Связь с другими классами сложности

Из определения непосредственно следует, что S ^П
₂ замкнут относительно объединений, пересечений и дополнений. Сравнивая определение с определением $\Sigma _{2}^{P}$ и $\Pi _{2}^{P}$ , отсюда также сразу следует, что S ^П
₂ содержится в $\Sigma _{2}^{P}\cap \Pi _{2}^{P}$ . Фактически это включение можно усилить до ЗПП. ^{НАПРИМЕР}. ^[1]

Каждый язык в NP также принадлежит S ^П
₂ . По определению, язык L находится в NP, если и только если существует верификатор V ( x , y ) с полиномиальным временем, такой, что для каждого x в L существует y , для которого V отвечает true, и такой, что для каждого x нет в L , V всегда отвечает ложно. Но такой верификатор легко трансформируется в S ^П
₂ предиката P ( x , y , z ) для того же языка, который игнорирует и в остальном ведет себя так же, как V. z Тем самым ко-NP принадлежит S ^П
₂ . Эти простые включения можно усилить, показав, что класс S ^П
₂ содержит MA (по обобщению теоремы Сипсера–Лаутмана ) и $\Delta _{2}^{P}$ (в более общем смысле, $P^{{\mathsf {S}}_{2}^{P}}={\mathsf {S}}_{2}^{P}$ ).

Теорема Карпа – Липтона

Версия теоремы Карпа – Липтона утверждает, что если каждый язык в NP имеет схемы полиномиального размера , то иерархия полиномиального времени схлопывается до S ^П
₂ . Этот результат приводит к усилению теоремы Каннана : известно, что S ^П
₂ не содержится в SIZE ( n ^к) для любого фиксированного k .

Симметричная иерархия

В качестве расширения можно определить ${\mathsf {S}}_{2}$ как оператор по классам сложности; затем ${\mathsf {S}}_{2}P={\mathsf {S}}_{2}^{P}$ . Итерация $S_{2}$ оператор дает «симметричную иерархию»; объединение классов, созданных таким образом, равно Полиномиальной иерархии .

Ссылки

^ Цай, Джин-И (2007), " $\mathrm {S} _{2}^{p}\subseteq \mathrm {{ZPP}^{NP}}$ ( PDF ) , Journal of Computer and System Sciences , 73 (1): 25–35, doi : 10.1016/j.jcss.2003.07.015 , MR 2279029. Предварительная версия этой статьи появилась ранее, в FOCS 2001, ECCC . ТР01-030 , МР 1948751 , дои : 10.1109/SFCS.2001.959938 .

Канетти, Ран (1996). «Подробнее о BPP и иерархии полиномиального времени». Письма об обработке информации . 57 (5). Эльзевир: 237–241. дои : 10.1016/0020-0190(96)00016-6 .
Рассел, Александр; Сундарам, Рави (1998). «Симметричное чередование захватывает БПП». Вычислительная сложность . 7 (2). Биркхойзер Верлаг: 152–162. дои : 10.1007/s000370050007 . ISSN 1016-3328 . S2CID 15331219 .

Внешние ссылки

Зоопарк сложности : S ₂ P
Класс сложности недели: S ₂^П , Лэнс Фортноу 28 августа 2002 г.

[1] Цай, Джин-И (2007), " $\mathrm {S} _{2}^{p}\subseteq \mathrm {{ZPP}^{NP}}$ ( PDF ) , Journal of Computer and System Sciences , 73 (1): 25–35, doi : 10.1016/j.jcss.2003.07.015 , MR 2279029. Предварительная версия этой статьи появилась ранее, в FOCS 2001, ECCC . ТР01-030 , МР 1948751 , дои : 10.1109/SFCS.2001.959938 .

[1]