S2P (сложность)
В теории сложности вычислений SР
2— класс сложности , промежуточный между первым и вторым уровнями полиномиальной иерархии . Язык L находится в , если существует полиномиальный предикат P такой, что
Из определения сразу следует, что SР
2замкнут относительно объединений, пересечений и дополнений. Сравнивая определение с определением и , также сразу следует, что SР
2содержится в . Это включение фактически можно усилить до ЗПП НП . [1]
Каждый язык в NP также принадлежит SР
2. Ведь по определению язык L находится в NP тогда и только тогда, когда существует полиномиально-временной верификатор V ( x , y ), такой, что для каждого x в L существует y , для которого V отвечает true, и такой, что для каждого x не в L , V всегда отвечает ложью. Но такой верификатор может быть легко преобразован в SР
2предикат P ( x , y , z ) для того же языка, который игнорирует z и в остальном ведет себя так же, как V . Точно так же ко-NP принадлежит SР
2. Эти простые включения можно усилить, чтобы показать, что класс SР
2содержит MA (в силу обобщения теоремы Зипсера–Лаутемана ) и (в более общем случае ).
Версия теоремы Карпа – Липтона утверждает, что если каждый язык в NP имеет схемы полиномиального размера, то иерархия полиномиального времени схлопывается до SР
2. Этот результат дает усиление теоремы Каннана : известно, что SР
2не содержится в SIZE ( n k ) ни для какого фиксированного k .
В качестве расширения можно определить как оператор на классах сложности; тогда . Итерация оператора дает «симметричную иерархию»; объединение классов, созданных таким образом, равно полиномиальной иерархии .
