discretization

メモ。Miklos Ajtai and Cynthia Dwork "A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence"のAppendix1のp19んところにあり。
we must charge time \theta(n^{e_1}) for B(186註:oracle付確率的多項式アルゴリズム) to access a 2^{-n^{e_0}} approximation to a real input.か。とんでp28に離散化しても問題無いし、多項式時間で解けると書いて証明終了の様子。
成る程、こういう風に定義すると扱い易いのか。つぅか、T先生の専門分野じゃ……ないな、微妙にずれてるよなぁ。