¿Un problema natural en

10

La clase de complejidad se define de la siguiente manera (de Wikipedia ):S2P

Un lenguaje está en si existe un predicado de tiempo polinómico tal queLS2PP

  • Si , entonces existe una tal que para todo ,xLyzP(x,y,z)=1
  • Si , entonces existe una tal que para todo ,xLzyP(x,y,z)=0

donde el tamaño de y debe ser polinomial en el tamaño de .yzx

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?S2PS2P

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 .S2PS2P

Robin Kothari
fuente
3
¿Qué tal "un número impar de estos circuitos son satisfactorios"?
3
Este es un buen ejemplo, sin embargo, también está en la clase más pequeña . Δ2=PNP
sdcvvc
44
No es exactamente lo que pediste, pero ¿qué tal un problema completo para promesa? ? Fortnow - Impagliazzo - Kabanets - Umans, Sobre la complejidad de los sucintos juegos de suma cero, Computational Complexity 17: 353-376, 2008, ver cs.sfu.ca/~kabanets/Research/games.htmlS2p
Joshua Grochow
1
@RickyDemer: Gracias, ese es un buen ejemplo. (Si entiendo correctamente, es igualmente fácil demostrar que el problema también está en ).Δ2
Robin Kothari
@ JoshuaGrochow: Gracias, eso funciona para mí. Siéntase libre de publicar eso como respuesta. Parece la mejor respuesta hasta ahora, pero esperaré para ver si obtengo una mejor.
Robin Kothari

Respuestas:

8

¿Qué tal un problema completo para promesa- ?S2p

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.S2pS2p

(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).S2pMAPNPS2pBPPPH

Joshua Grochow
fuente