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