¿Existe una versión continua del teorema de repetición paralela?

El teorema de la pretición paralela de Raz es un resultado importante en PCP, aproximación, etc. El teorema se resume de la siguiente manera.

$G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi, V)$ $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ $\pi$ $\mathcal{S}\times\mathcal{T}$ $V:\mathcal{S}\times\mathcal{T}\times\mathcal{A}\times\mathcal{B}\rightarrow\{0,1\}$

v (G) = max_{h_{A} \in H_{A}, h_{B} \in H_{B}} \sum_{s, t} π (s, t) V (s, t, h_{A} (s), h_{B} (t))

$v(G)=\max_{h_A\in\mathcal{H}_A,h_B\in\mathcal{H}_B}\sum_{s,t}\pi(s,t)V(s,t,h_A(s),h_B(t))$

n

$n$ juego doble . El teorema dice si entonces .

G^{n} = (S^{n}, T^{n}, A^{n}, B^{n}, π^{n}, V^{n})

$G^n=(\mathcal{S}^n,\mathcal{T}^n,\mathcal{A}^n,\mathcal{B}^n,\pi^n, V^n)$

v (G) \leq 1 - ϵ,

$v(G)\leq 1-\epsilon,$

v (G^{n}) \leq (1 - ϵ^{c})^{Ω (\frac{n}{\log max {| A |, | B |}})}

$v(G^n)\leq (1-\epsilon^c)^{\Omega(\frac{n}{\log\max\{|A|,|B|\}})}$

Mi pregunta es qué sucede si los conjuntos son infinitos, en un espacio continuo. Digamos si son subconjuntos de un espacio, digamos , o más espacios abstractos. Todo lo demás es igual. El teorema de Raz solo da un límite superior trivial ya que los tamaños de los conjuntos de respuestas son infinitos. Obviamente, el valor pliegue está limitado por una sola copia. ¿La disminución exponencial también ocurre en caso continuo? ¿Sería más interesante restringir para que sean colecciones de funciones continuas o funciones o funciones medibles? $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ $R^n$ $1$ $n$ $\mathcal{H}_A,\mathcal{H}_B$ $C^{\infty}$

cc.complexity-theory complexity-classes pcp interactive-proofs pyao
fuente

Respuestas:

¿La disminución exponencial también ocurre en caso continuo?

No. Feige y Verbitsky [FV02] mostraron que por cada n , hay un juego G (con conjuntos finitos de preguntas y respuestas) tal que v ( G ) ≤3 / 4 y v ( G ⁿ ) ≥1 / 8. Debido a que su formulación generaliza juegos con conjuntos finitos de preguntas y respuestas de cualquier tamaño, la repetición paralela (de muchas veces) no puede disminuir el valor de un juego de 3/4 a 1/8.

[FV02] Uriel Feige y Oleg Verbitsky. Reducción de errores por repetición paralela: un resultado negativo. Combinatorica , 22 (4): 461–478, octubre de 2002. doi: 10.1007 / s00493-002-0001-0 .

Tsuyoshi Ito
fuente