Gibt es eine kontinuierliche Version des Satzes der parallelen Wiederholung?

Der parallele Pretitionssatz von Raz ist ein wichtiges Ergebnis bei PCP, Inapproximation usw. Der Satz ist wie folgt gegliedert.

Ein Spiel , wobei endliche Mengen sind, eine Verteilung auf ist und das Prädikat . Definiere den Wert des Spiels $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\}$ und-fach Spiel

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$

. Der Satz besagt, wenn

dann ist

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

Meine Frage ist, was passiert, wenn die Mengen unendlich sind, in einem zusammenhängenden Raum. Sagen Sie, wenn Teilmengen eines Raums sind, sagen Sie oder mehrere abstrakte Räume. Alle anderen sind gleich. Der Satz von Raz gibt nur eine triviale Obergrenze da die Größe der Antwortmengen unendlich ist. Offensichtlich ist der fache Wert durch eine einzelne Kopie nach oben begrenzt. Kommt es auch im Dauerbetrieb zu einer exponentiellen Abnahme? Wäre es interessanter, auf Sammlungen von stetigen Funktionen oder -Funktionen oder messbaren Funktionen zu beschränken? $\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
quelle

Gibt es eine kontinuierliche Version des Satzes der parallelen Wiederholung?

Antworten: