Ein natürliches Problem in

Die Komplexitätsklasse ist wie folgt definiert (aus Wikipedia ):$\textrm{S}_2^\textrm{P}$

Eine Sprache ist in S P 2, wenn ein Polynom-Zeit-Prädikat P existiert, so dass$L$$S_2^P$$P$

• Wenn , existiert ein y, so dass für alle z , P ( x , y , z ) = $x \in L$$y$$z$$P(x,y,z)=1$
• Wenn , so gibt es eine z so daß für alle y , P ( x , y , z ) = $x \notin L$$z$$y$$P(x,y,z)=0$

wobei die Größe von und z in der Größe von x polynomisch sein muss .$y$$z$$x$

Weitere informelle Erklärungen und Diskussionen finden Sie in Fortnows Beitrag und im Komplexitätszoo .

Obwohl diese Klasse einigermaßen natürlich erscheint, kann ich aus einem nicht trivialen Grund kein Beispiel für ein Problem in (dh nicht nur, weil es in NP oder MA oder einer in S P 2 enthaltenen Klasse ist ). Kennt jemand ein Problem, das dieser Beschreibung entspricht?$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

Wenn sich niemand ein solches Problem vorstellen kann, würde mir ein Problem in einer Unterklasse von nichts ausmachen , aber es ist nicht trivial, dies zu zeigen, während das Problem offensichtlich in S P 2 liegt .$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

$\mathsf{S_2^p}$

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets und Chris Umans. Über die Komplexität prägnanter Nullsummenspiele . Computational Complexity 17: 353 & ndash; 376, 2008.

Aus der Zusammenfassung:

$\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}$