計算理理論論⼊入⾨門 第7回 平成27年年6⽉月1⽇日 河村彰星 諸性質→ 問7.1 http://www.graco.c.u-tokyo.ac.jp/~kawamura/teaching/k3/ NP完全 定義 判定問題 𝐵 が 𝐍𝐏 困難とは 任意の 𝐴 ∈ 𝐍𝐏 が 𝐵 に帰着する（𝐴 ≤𝐏 𝐵）こと 𝐍𝐏 完全とは 𝐍𝐏 に属し 𝐍𝐏 困難であること ≤𝐏 ≤𝐏 ≤𝐏 𝐍𝐏 完全 𝐏 𝐜𝐨𝐍𝐏 𝐜𝐨𝐍𝐏 完全 「NP問題のうち最難」 𝐍𝐏 完全問題 問7.2 ※本当は帰着を指定して 𝐍𝐏-≤𝐏 困難とか⾔言うべきだが略略することにする 𝐍𝐏 まとめ SAT，IS など 多くの問題 𝐍𝐏 だが（P=NPでない限り）空ではない 問7.7 じつは ここ（ 𝐍𝐏 ∖ 𝐏 ∖ 𝐍𝐏完全）にありそうな問題の⽅方が むしろ⾒見見つけにくい 𝑥 級 𝐍𝐏（前回） 𝑟 機械 𝑀 受理理 𝑀 𝑥, 𝑟 （⾃自信あり） 拒否 （取りあえず） ⽚片側誤り 誤受理理なし 誤拒否あり のとき 𝑀 𝑥, 𝑟 𝑀 𝑥, 𝑟 は必ず拒否 は受理理することがある （或る 𝑟 については） 定義 nondeterministic の N 判定問題 𝐴 が 𝐍𝐏 に属するとは 多項式時間限定の（⾮非決定性）機械 𝑀 が存在し 任意の⼊入⼒力力 𝑥 に対し 𝐴 𝑥 =真 のとき ※判定問題についてのみ意味をなす定義 （如何なる 𝑟 についても） 𝐴 𝑥 =偽 ≤𝐏 𝐍𝐏 困難 𝐵 𝐏 に属する 𝐍𝐏 に属する （𝐏 = 𝐍𝐏 であるか否かは未解決 百万ドル） 𝑟 は 𝐴 𝑥 = 真 であることの「証拠」 𝐏 ⊆ 𝐍𝐏 𝐏 に属する 𝐍𝐏 に属する 𝐴 𝐍𝐏 困難 これを使って多くの問題の 𝐍𝐏 困難性が⽰示される つまり… 連絡 今回 問7.1は必ず出して下さい 採点 先週提出分は返却済 （⾬雨天なら翌⽇日に順延） 6⽉月9⽇日（⽕火）14時〜～ キャンパス環境整備に御協⼒力力を 多対⼀一帰着（前々回） 定義 判定問題 𝐴 が判定問題 𝐵 に 多項式時間多対⼀一帰着するとは 函数 𝑇 ∈ 𝐅𝐏 が存在して 任意の 𝑥 ∈ dom 𝐴 に対し 𝑇 𝑥 ∈ dom 𝐵 と 𝐴 𝑥 = 𝐵(𝑇 𝑥 ) が成⽴立立つことをいう 「𝐵 を使うと 𝐴 が計算できる」 「𝐴 の難しさは 𝐵 以下」 ≤𝐏 IS 𝐍𝐏 完全 𝐍𝐏 完全 3SAT 問7.3 値 を計算する機械 𝑇 値 𝐴 ≤𝐏 𝐵 と書く 𝐴 の個例例 𝐵 の個例例 𝐵 𝐴 を計算する機械 VC 𝐍𝐏 完全 CLQ 𝐍𝐏 完全 問7.4 問7.5 帰着により様々な問題の 𝐍𝐏 完全性が順次⽰示される 更更に⾊色んな例例→ ≤𝐏 与えられた回路路が充⾜足可能か判定せよ 与えられた無向グラフ 𝐺 と整数 𝑙 とに対し 𝐺 に⼤大きさ 𝑙 以上の独⽴立立集合があるか判定せよ 推移律律を満す（𝐴 ≤𝐏 𝐵 ≤𝐏 𝐶 ならば 𝐴 ≤𝐏 𝐶） 例例 問題 IS 問題 CSAT CSAT 𝐍𝐏 完全 機械の動きが回路路で 表されることから（資料料）
© Copyright 2024 ExpyDoc
