¿Un problema natural en

La clase de complejidad se define de la siguiente manera (de Wikipedia ):$\textrm{S}_2^\textrm{P}$

Un lenguaje está en si existe un predicado de tiempo polinómico tal que$L$$S_2^P$$P$

• Si , entonces existe una tal que para todo ,$x \in L$$y$$z$$P(x,y,z)=1$
• Si , entonces existe una tal que para todo ,$x \notin L$$z$$y$$P(x,y,z)=0$

donde el tamaño de y debe ser polinomial en el tamaño de .$y$$z$$x$

También vea la publicación de Fortnow y el zoológico de complejidad para obtener explicaciones y discusiones más informales.

Si bien esta clase parece razonablemente natural, no puedo encontrar un ejemplo de un problema que esté en por una razón no trivial (es decir, no solo porque está en NP o MA o alguna clase contenida en ). ¿Alguien sabe un problema que se ajuste a esta descripción?$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

Si nadie puede pensar en un problema como ese, no me importaría un problema que esté en una subclase de , pero no es trivial mostrar esto, mientras que el problema obviamente está en S P 2 .$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

¿Qué tal un problema completo para promesa- ?$\mathsf{S_2^p}$

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets y Chris Umans. Sobre la complejidad de los sucintos juegos de suma cero . Complejidad computacional 17: 353-376, 2008.

Del resumen:

Demostramos que la aproximación del valor de un juego sucinto de suma cero a un factor aditivo está completa para la promesa de clase: , la versión "prometida" de S p 2 . Hasta donde sabemos, es el primer problema natural que se muestra completo para esta clase.$\mathsf{S_2^p}$$\mathsf{S_2^p}$

(Nota histórica: no es demasiado sorprendente que se sepa que no hay muchos problemas naturales en pero no se sabe que están en sus subclases M A o P N P. Si revisa los documentos originales de Russell - Sundaram y Canetti (independientemente), parece que la definición de S p 2 se hizo más o menos específicamente para capturar sus argumentos mejorados colocando B P P en P H , en lugar de capturar algún conjunto de problemas naturales).$\mathsf{S_2^p}$$\mathsf{MA}$$\mathsf{P^{NP}}$$\mathsf{S_2^p}$$\mathsf{BPP}$$\mathsf{PH}$