Existe-t-il une version continue du théorème de répétition parallèle

Le théorème de prétention parallèle de Raz est un résultat important dans le PCP, l'inapproximation, etc. Le théorème est fomalisé comme suit.

Un jeu , où sont des ensembles finis, est une distribution sur et un prédicat . Définir la valeur du jeu $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_{UNE} \in H_{UNE}, h_{B} \in H_{B}} \sum_{s, t} π (s, t) V (s, t, h_{UNE} (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$

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

My quesion is what happen if the sets are infinite, in a continuous space. Say if $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ are subsets of a space, say $R^n$ , or more abstract spaces. All the rest are same. Raz's theorem only gives a trivial upper bound $1$ since the sizes of answer sets are infinite. Obviously $n$ -fold value is upper bounded by single copy. Does exponential decrease also happen in continuous case? Would it be more interesting to restrict $\mathcal{H}_A,\mathcal{H}_B$ to be collections of continuous functions or $C^{\infty}$ functions or measureable functions?

cc.complexity-theory complexity-classes pcp interactive-proofs pyao
la source

Réponses:

Does exponential decrease also happen in continuous case?

Non. Feige et Verbitsky [FV02] ont montré que pour chaque n , il y a un jeu G (avec des ensembles finis de questions et réponses) tel que v ( G ) ≤3 / 4 et v ( G ⁿ ) ≥1 / 8. Parce que votre formulation généralise les jeux avec des ensembles finis de questions et réponses de toute taille, la répétition parallèle (de plusieurs fois) ne peut pas diminuer la valeur d'un jeu de 3/4 à 1/8.

[FV02] Uriel Feige et Oleg Verbitsky. Réduction des erreurs par répétition parallèle - Un résultat négatif. Combinatorica , 22 (4): 461–478, octobre 2002. doi: 10.1007 / s00493-002-0001-0 .

Tsuyoshi Ito
la source