Существует ли непрерывная версия теоремы о параллельном повторении?

Теорема Раза о параллельном предсказании является важным результатом в PCP, аппроксимации и т. Д. Теорема оформилась следующим образом.

Игра , где - конечные множества, - распределение по и предикат . Определить значение игры $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$

. Теорема говорит, что если

то

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

Мой вопрос: что произойдет, если множества бесконечны в непрерывном пространстве? Скажем, если являются подмножествами пространства, скажем, или более абстрактных пространств. Все остальные одинаковы. Теорема Раза дает только тривиальную верхнюю границу поскольку размеры множеств ответов бесконечны. Очевидно, кратное значение ограничено сверху одной копией. Экспоненциальное уменьшение также происходит в непрерывном случае? Было бы более интересно , чтобы ограничить быть коллекции непрерывных функций или функции или измеряемых функций? $\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
источник

Ответы:

Экспоненциальное уменьшение также происходит в непрерывном случае?

Фейге и Вербицкий [FV02] показали, что для каждого n существует игра G (с конечным набором вопросов и ответов) такая, что v ( G ) ≤3 / 4 и v ( G ⁿ ) ≥1 / 8. Поскольку ваша формулировка обобщает игры с конечным набором вопросов и ответов любого размера, параллельное повторение (любого конечного числа раз) не может снизить ценность игры с 3/4 до 1/8.

[FV02] Уриэль Фейге и Олег Вербицкий. Уменьшение ошибок при параллельном повторении - отрицательный результат. Combinatorica , 22 (4): 461–478, октябрь 2002 г. doi: 10.1007 / s00493-002-0001-0 .

Цуёси Ито
источник