Естественная проблема в

Класс сложности определяется следующим образом (из Википедии ):$\textrm{S}_2^\textrm{P}$

Язык находится в S P 2, если существует предикат P полиномиального времени, такой что$L$$S_2^P$$P$

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

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

Также см. Сообщение Fortnow и зоопарк сложности для более неформальных объяснений и обсуждений.

Хотя этот класс кажется достаточно естественным, я не могу найти пример проблемы, которая находится в по нетривиальной причине (т. Е. Не только потому, что она находится в NP или MA или каком-либо классе, содержащемся в S P 2 ). Кто-нибудь знает проблему, которая подходит под это описание?$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

Если никто не может придумать такую ​​проблему, я не возражаю против проблемы, которая относится к подклассу , но показать это нетривиально, тогда как проблема явно в S P 2 .$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

Как насчет задачи, полной для обещания - ?$\mathsf{S_2^p}$

Лэнс Фортноу, Рассел Импальяццо, Валентин Кабанец и Крис Уманс. О сложности кратких игр с нулевой суммой . Вычислительная сложность 17: 353-376, 2008.

Из аннотации:

$\mathsf{S_2^p}$$\mathsf{S_2^p}$

$\mathsf{S_2^p}$$\mathsf{MA}$$\mathsf{P^{NP}}$$\mathsf{S_2^p}$$\mathsf{BPP}$$\mathsf{PH}$