Los juegos de dos rondas y una ronda (2P1R) son una herramienta esencial para la dureza de la aproximación. Específicamente, la repetición paralela de juegos de una ronda de dos probadores ofrece una forma de aumentar el tamaño de una brecha en la versión de decisión de un problema de aproximación. Vea la charla de encuesta de Ran Raz en CCC 2010 para obtener una descripción general del tema.
La repetición paralela de un juego tiene la sorprendente propiedad de que, si bien un verificador aleatorio funciona de manera independiente, los dos jugadores pueden jugar los juegos de forma no independiente para lograr un mayor éxito que jugar cada juego de forma independiente. La cantidad de éxito está limitada anteriormente por el teorema de repetición paralela de Raz:
Teorema : existe una constante universal modo que por cada juego 2P1R con valor y tamaño de respuesta , el valor del juego de repetición paralela es como máximo .
Aquí hay un resumen del trabajo de identificación de esta constante :
- El trabajo original de Raz prueba .
- Holenstein mejoró esto a .
- Rao demostró que suficiente (y se elimina la dependencia de ) para el caso especial de los juegos de proyección.
- Raz dio una estrategia para el juego de ciclo impar que mostró que el resultado de Rao es agudo para los juegos de proyección.
Por este cuerpo de trabajo, sabemos que . Mis dos preguntas son las siguientes:
Pregunta 1: ¿Los expertos en esta área tienen un consenso para el valor exacto de ?
Si se piensa que , ¿hay juegos específicos que no sean proyectivos, pero que también violen específicamente las propiedades adicionales de los juegos de proyección que requiere la prueba de Rao?
Según mi propia lectura, parece que la propiedad más importante de los juegos de proyección que usa Rao es que una buena estrategia para la repetición paralela no usaría muchas de las respuestas posibles para ciertas preguntas. Esto está relacionado de alguna manera con la localidad de los juegos de proyección.
fuente