Feige-Shamirの論文とGoldreichの教科書で定義が違うことに気付いた. ともに任意のnの多項式程度の長さのz, 任意のPPTM V^*について下記を満たすある無視できる関数 ε が存在することとなっている. Goldreichの方だと, D_nを{0,1}^n上の分布, XをD_nに従う確…
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。