$ textbf {PCP} [poly(n)、O(1)] = textbf {coRP} $ですか?

最近何かが私に鳴り響いています。これは、$ textbf {PCP} [poly(n)、0] = textbf
{coRP} $であるが、$ textbf {PCP} [poly(n)、O(1)] = textbf {coRP}
$?

私はこの声明の証拠を見つけましたが、何かが間違っていると感じています。ここに行く:

textbf {PCP} [poly(n)、O(1)] $に$ Lを置く。 $ poly(n)$ランダムコインを反転し、$
q $が定数である証明書から$ q $ビットを読み取る$ L $に対する検証者$ V $があります。

$ q $ビットの証明クエリは、$ 2 ^ q $の可能な値を返すことができます。私の考えは$ 2 ^ q $の$ V
$コピーをシミュレートすることによって$ L $に対して$ textbf {coRP}
$アルゴリズムを構築することです。各コピーには証明書照会とは異なる答えが与えられます。 $ V
‘$のコピーの少なくとも1つが受け入れるならば、$ V’ $は受け入れます。

入力が$ L $の場合、証明書が存在し、$ V $は完全な完全性を受け入れます。その証明書からの照会ビットは必然的に$ 2 ^
q $の可能な値になるので、$ V $のシミュレートされたコピーの少なくとも1つが完全な完全性を受け入れます。

If the input is not in $L$, then all copies have probability
< 1 of accepting. Thus $V’$ has some probability $rho < 1$
of accepting.

増幅を使用して、$ ρ$〜$ frac {1} {2} $を$ textbf {coRP}
$の定義に一致するように高めることができます。

この証明は正しいですか?

ベストアンサー

PCP定理を想起すると、$ PCP(log(n)、1)$は既にNPであり、実際に$ PCP(poly(n)、1)$は$ NEXP
$です。

あなたの証明の問題は、長さ$ 2 ^ q
$の文字列に対してcoRPアルゴリズムをシミュレートできないことです。それはqビットにしかアクセスしませんが、アクセスするビットはランダムコインに依存します。あなたは特定のコインの結果を考えるべきではありませんが、それらのすべてはインプット上にあります。それは基本的にあなたの証明がうまくいかない理由です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です