計算量量 理理論論
平成26年年11⽉月18⽇日代講河村彰星（今井研助教）http://www-imai.is.s.u-tokyo.ac.jp/~kawamura/teaching/0510021/ 先週の続きは次回
乱択
𝑧−𝑥𝑥+𝑦𝑦𝑦+𝑧𝑧−𝑥𝑥𝑦𝑧+𝑥𝑦𝑧+𝑥𝑦−𝑧−𝑥−𝑧𝑥𝑥+𝑥𝑦−𝑦𝑧𝑥+𝑦−𝑧+𝑥𝑦𝑦𝑧+𝑥+𝑦𝑦𝑧−𝑥+𝑦𝑥+𝑦−𝑧−𝑥−𝑧𝑥𝑦+𝑥𝑧+𝑦𝑧𝑥+𝑦−𝑧+𝑥−𝑦𝑥+𝑧(𝑦+𝑧)(𝑦−𝑧)+𝑦𝑦𝑧𝑧
与えられた整数係数多項式が零零 か判定
⽂文字式のまま全部展開して計算
適当に数値 を 代⼊入して計算し
0になる か調べ る ⼤大変 ラク（⾼高速） ⾼高確率率率で正解 例例
乱数を利利⽤用した計算𝑥,𝑦,𝑧=(1,2,3)とか
⾮非決定性（＝乱択）機械
時間量量が𝜏:𝐍→𝐍とは任意の𝑥と任意の𝒓について𝜏(|𝑥|)時間以内で停⽌止すること
次の遷移を複数の分岐から ⾮非決定的 に
（等確率率率で）選ぶ
初めに「乱数テープ」上に 乱数 列列が
無限に供給される 通常テープ ０００１１０１１０１１０１０００１１０１０１１０１１……乱数テープ遷移規則𝛿︓：𝑄×𝛴𝑄×𝛴×㊧,㊨ ×𝛴 常に㊨へ
計算結果
𝑀 𝑥 , 𝑟
𝑟=⼊入⼒力力乱数 機械𝑀
に依存 𝜏𝑥ビットで⼗十分
定義 判定問題 𝐴 が級 𝐑𝐏 に属する とは 或る多項式時間（乱択）機 械 𝑀 が存在し 任意の⼊入⼒力力 𝑥 に対し
𝐴 𝑥 = 真 𝑀 𝑥 ,𝑟 は 確率率率 >
𝟏𝟐
で 受理理
のとき𝐴 𝑥 = 偽 𝑀 𝑥 ,𝑟 は 必ず 拒否
のとき 「> 0
」にすると𝐍𝐏
⽚片側誤り
の代りににしたければ…
𝑀 𝑥 ,
𝑟機械𝑀𝑥
𝑟受理理
（確信︕！）拒否
（多分…）𝑀𝑥,𝑟, …, 𝑀𝑥,𝑟のうち⼀一つ以上が受理理したら受理理 乱数を独⽴立立に7 回取って𝑟,…,𝑟 誤受理理なし誤拒否あり
randomizedのR
𝐏 ⊆ 𝐑𝐏 ⊆ 𝐍𝐏 NP とか RP とかの 定義につい て
定義機械が決定的多項式時間限定であるとは…
定義機械𝑀が問題𝐴を計算するとは…
𝐏
定義機械が⾮非決定的多項式時間限定であるとは…
𝐍𝐏
定義機械𝑀が問題𝐴を計算するとは…こうではない
定義機械𝑀が問題𝐴を計算するとは… 定義機械が乱択的多項式時間限定であるとは…
𝐑 𝐏
こうではない 注意「多項式時間で決定的 に 解けるの が 𝐏 」
「多項式時間で⾮非決定的に解け るのが 𝐍𝐏 」
「多項式時間で乱 択 で解けるの が 𝐑𝐏 」
定義機械が多項式時間限定であるとは…定義機械𝑀が問題𝐴を●●●するとは…
𝐏
定義⾮非決定性機械が多項式時間限定であるとは…
𝐍𝐏
定義機械𝑀が問題𝐴を計算するとは…↑ここを変える↑こっちは殆ど同じ
𝐁𝐏𝐏 𝐙 𝐏𝐏 𝐏 𝐏
⋮ 「多項式時間で決定的 に 解けるの が 𝐏 」
「多項式時間で⾮非決定的に解け るのが 𝐍𝐏 」
「多項式時間で乱 択 で解けるの が 𝐑𝐏 」
定義機械𝑀が問題𝐴を▲▲▲するとは… 定義⾮非決定性機械が多項式時間限定であるとは…𝐑 𝐏
他にも⾊色々𝐔𝐏 # 𝐏 NP とか RP とかの 定義につい て
注意算法
𝑝 が零零な ら確実に 拒否 ⾮非零零 なら次の補題に より 確率率率 > で受理理 数 𝑟 ,… ,𝑟 ∈ 1 ,… ,2𝑑 を⼀一様独⽴立立に乱 択 し 𝑝 𝑟 ,… ,𝑟 ≠ 0 ならば 受理理
𝑑は𝑝の全次数問題 与えられた整数 係数多項 式 𝑝 𝑋 ,… ,𝑋 が
⾮非零零である か 判定せよ 𝐏 に属するかは 未解決だが 次の算法により 𝐑𝐏 に 属する
（多項式零零判定が𝐜𝐨𝐑𝐏に属する）補題 全次数 𝑑 の⾮非零零多項 式 𝑝 について
Pr 𝑝 𝑟 ,𝑟 ,… ,𝑟 ≠ 0 ≥ 1 − 𝑑 𝐵
但し確率率率は𝑟,𝑟,…,𝑟∈1,…,𝐵を無作為に取ったもの証明
𝑚に関する帰納法𝑚>0とする𝑋の次数を𝑖として𝑝𝑋,𝑋,…,𝑋=𝑋⋅𝑞𝑋,…,𝑋+𝑋の低次の項と書く帰納法の仮定よりPr𝑞𝑟,…,𝑟≠0≥1−もしならば𝑝𝑋,𝑟,…,𝑟は𝑋に関する𝑖次の⾮非零零な多項式でその根は⾼高々𝑖個故に
Pr≥Pr⋅1− 𝑖𝐵 ≥1− 𝑑−𝑖𝐵 1− 𝑖𝐵 ≥1− 𝑑𝐵
定義 判定問題 𝐴 が級 𝐁𝐏𝐏 に属する とは 或る多項式時間（乱択）機 械 𝑀 が存在し 任意の⼊入⼒力力 𝑥 に対し
𝐴 𝑥 = 真 𝑀 𝑥 ,𝑟 は 確率率率 >
𝟐𝟑
で 受理理
のとき𝐴 𝑥 = 偽 𝑀 𝑥 ,𝑟 は 確率率率 >
𝟐𝟑で 拒否
のとき>
ではダメ 両側誤り
の代りににしたければ…
𝑀 𝑥 ,
𝑟機械𝑀𝑥
𝑟受理理
（多分…）拒否
（多分…）𝑀𝑥,𝑟, …, 𝑀𝑥,𝑟の多数決で受理理・拒否 乱数を⼗十分な回数取って𝑟,…,𝑟 誤受理理あり誤拒否あり
bounded probabilistic
𝐑𝐏 ⊆ 𝐁𝐏𝐏 𝐁𝐏𝐏 = 𝐜𝐨𝐁𝐏𝐏
定義 判定問題 𝐴 が級 𝐙𝐏𝐏 に属する とは 或る多項式時間（乱択）機 械 𝑀 が存在し 任意の⼊入⼒力力 𝑥 に対し 𝐴 𝑥 = 真 𝑀 𝑥 ,𝑟 は 必ず 受理理
または「︖？」
のとき𝐴 𝑥 = 偽 𝑀 𝑥 ,𝑟 は 必ず 拒否
または「︖？」
のとき 無誤り
（︖？）繰返せば<にもできる
𝑀 𝑥 ,
𝑟機械𝑀𝑥
𝑟受理理
（確実）拒否
（確実） 誤受理理なし誤拒否なしzero-error ワカリマセン
「︖？」 の確率率率は常に <
決着がつくまで繰返す → 時間の期待値 po ly 𝑥 定理理 𝐙𝐏𝐏 = 𝐑𝐏 ∩ 𝐜𝐨𝐑𝐏
証明
受理理（確実︕！）
拒否（微妙…） 受理理（微妙…）
拒否（確実︕！） 信⽤用「︖？」 「︖？」信⽤用 𝐑𝐏
∩
𝐜𝐨𝐑𝐏⊆ 𝐙𝐏𝐏 𝐙𝐏𝐏 ⊆ 𝐑𝐏
「︖？」の代りに拒否𝐙𝐏𝐏 ⊆ 𝐜𝐨 𝐑𝐏
「︖？」の代りに受理理両⽅方の算法を実⾏行行してみて現実 に解ける 𝐏 = まあ⼤大体
現実 に解ける
（真の乱数があれば）𝐁𝐏𝐏 =どれほど重要なのか︖？0と1が確率率率ちょうどで出る乱数であることどうでもよい。例例えば「〜～の未知の確率率率で
1が出るとわかっている」乱数があれば何とかなる。
乱数の量量 乱数の各ビットがそれなりに独⽴立立であること或る程度度は重要。前のビットから完全に決ってしまうようでは役⽴立立たず。
或る程度度は重要。Olog𝑛ビットなら代りに決定的に全部試せる。 本当に異異なるのか︖？
𝑟𝑟𝑟𝑟𝑟𝑟𝑟
𝑟 ⻑⾧長さ𝑡𝑛の乱数列列
⋮
𝐴 ∈ 𝐁𝐏 𝐏
とすると多項式時間機械𝑀が存在して任意の⼊入⼒力力𝑥（⻑⾧長さ𝑛）について（𝑀𝑥,𝑟≠𝐴(𝑥)なる𝑟の割合） ○○○○×○○○ ⋮ 𝑥○×○○○○×○ ⋮ 𝑥×○○○○○○○ ⋮ 𝑥 ⻑⾧長さ𝑛の⽂文字列列
○×○○○○○
○ ⋮ 𝑥…
全部○の⾏行行（⻑⾧長さ𝑛の⼊入⼒力力すべてで𝑀を正解させる乱数）が存在︕！
𝐴 ∈ 𝐏 /po ly
多項式時間機械＋少量量の助⾔言𝐁𝐏𝐏は𝐏にかなり近い︖？実は等しいかも…︖？
誤り率率率 <
どの列列でも𝐍𝐏 𝐜𝐨𝐍𝐏
𝐁𝐏𝐏
𝐑𝐏𝐜𝐨𝐑𝐏 𝐙𝐏𝐏
𝐏
多項式の零零判定まとめ
𝐁𝐏𝐏 = 𝐏
未解決 ︖？（等しいと予想する⼈人が多い）
