計算理論入門 第9回 平成27年6月15日 河村彰星 http://www.graco.c.u-tokyo.ac.jp/~kawamura/teaching/k3/ 定義 空間量の制限 𝑥 = ０００１１０１１０１１ 入力テープ （書換え不可） ０００１１０１ 作業テープ 機械 𝑀 多項式空間 機械 𝑀 が 対数空間 限定とは 或る多項式 𝑝: 𝐍 → 𝐍 が存在し 任意の入力 𝑥 について （乱択機械においては更に、任意の乱数で） （停止し、それまでに） 作業テープ上で訪れる 枡目の個数 （入出力テープは度外視） ０００１１０１ 出力テープ （読取り不可） 出力を書く という代りに 今回 次回 受理 と考えることも 拒否 （判定問題の場合） が 𝑝 𝑥 以内であること log 𝑝 𝑥 入力よりも 小さい作業領域！ 「多項式」 = 𝑥 𝑂 1 = 2log 𝑥 「対数」 = O log 𝑥 定義 判定問題 𝐴 が級 𝐏𝐒𝐏𝐀𝐂𝐄 に属するとは 或る多項式空間限定の機械 𝑀 が 𝐴 を解くこと 「解く」の代りに 「N決定」にしたもの 𝐏 ⊆ 𝐏𝐒𝐏𝐀𝐂𝐄 = 𝐍𝐏𝐒𝐏𝐀𝐂𝐄 ⊆ 𝐄𝐗𝐏 自明 後で 後で 𝐏𝐒𝐏𝐀𝐂𝐄 に属する問題の例 命題変数 与えられた量化命題論理式 真（1）か偽（0）の値をとる 𝑄𝑛 𝑋𝑛 . 𝑄𝑛−1 𝑋𝑛−1 … 𝑄1 𝑋1 . 𝜑 𝑋1 , … , 𝑋𝑛 問題 QBF 例 の真偽を判定せよ ∃𝑋4 . ∀𝑋3 . ∃𝑋2 . ∀𝑋1 . 𝜑 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4 0 𝑋4 𝑋1 これが ∃ のみだと SAT ∃𝑋4 . ∀𝑋3 . ∃𝑋2 . ∀𝑋1 . 𝑋2 ∨ ¬𝑋3 ∧ 𝑋1 ∨ 𝑋4 ∨ 深 𝑋3 さ 𝑛 𝑋2 量化子（∀ か ∃） 1 ∧ 0 1 ∨ 0 ∀𝑋3 . ∃𝑋2 . ∀𝑋1 . 𝜑 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4 ∧ 0 ∨ 1 0 1 ∨ 1 0 QBF ∀𝑥. 𝜓 𝑥 ∃𝑋2 . ∀𝑋1=. 𝜑QBF 𝑋1 , 𝑋𝜓 2, 𝑋 4 QBF 𝜓 1 03 , 𝑋∧ ∨ 1 0 1 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 偽真偽真偽偽偽真真真真真偽偽真真 ∀𝜑 各葉の値は 0,0,1, 0 = 偽 容易に計算できる 葉 2𝑛 枚 QBF ∃𝑥. 𝜓 𝑥 ∀𝑋1 . 𝜑 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4 = QBF 𝜓 0 ∨ QBF 𝜓 1 𝜑 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4 深さ優先探索 空間量 O(𝑛) 𝐏𝐒𝐏𝐀𝐂𝐄 に属する問題の例 二人の試合（手数は多項式）の勝敗 例えば サメ メ 問題 SIRITORI 入力 字引（「ン」で終らない語の一覧） スズメ 出力 この中でしりとりをすると 先手必勝か？ ス カメ スルメ メダカ カケス カ カサ … 長さ poly 𝑥 ∃𝑟1 . ∀𝑟2 . ∃𝑟3 . … . ∀𝑟𝑛 . 𝐵 𝑥, 𝑟1 , 𝑟2 , 𝑟3 , … , 𝑟𝑛 うまく第一手 うまく第三手 を打てば どの第二手 を打てば に対しても ※ ∃𝑟1 だけだと 𝐍𝐏 … 先手の勝 である サ （𝐵 ∈ 𝐏） … 或る時点での状況を 完全に記述するには…… 時点表示グラフ 内部状態 機械 𝑀 に 𝑥 を入力して計算 𝑛 作業テープの内容 𝑥 = ０００１１０１１０１１ 入力テープ 𝑞∈𝑄 入力・作業テープの頭の位置 この組合せを時点表示と呼ぶ ０００１１０１ 作業テープ 機械 機械𝑀 𝑀 受 𝑀 が多項式空間 時点表示は 始 乱択機械では 分岐も 2poly 拒 𝑛 個 時点表示間の遷移関係 を表すグラフ 𝐺𝑀,𝑥 （𝑀 と 𝑥 から容易に作れる） 一つと しておく 定理 2poly 𝑛 (𝐍)𝐏𝐒𝐏𝐀𝐂𝐄 ⊆ 𝐄𝐗𝐏 多項式空間乱択機械の 時点表示グラフ 𝐺𝑀,𝑥 頂点数 2poly 時間 始 受 𝑥 拒 𝐺𝑀,𝑥 始 から 受 への路があるか調べればよい サヴィッチの定理（の一部） 𝐍𝐏𝐒𝐏𝐀𝐂𝐄 = 𝐏𝐒𝐏𝐀𝐂𝐄 多項式空間乱択機械の 時点表示グラフ 𝐺𝑀,𝑥 = 𝑉, 𝐸 頂点数 𝑉 = 2poly 始 𝑥 受 拒 「𝑢 から 𝑣 へ長さ 2𝑖 以下の路あり」を 𝑅 𝑢, 𝑣, 𝑖 と書くと 𝑅 𝑢, 𝑣, 𝑖 + 1 或る 𝑤 ∈ 𝑉 が存在して 𝑅 𝑢, 𝑤, 𝑖 かつ 𝑅 𝑤, 𝑣, 𝑖 𝑅 𝑢, 𝑣, 0 𝑢 = 𝑣 または 𝑢, 𝑣 ∈ 𝐸 これを再帰的に使って 𝑅 始 , 受 , log 𝑉 を計算 空間量 O log 𝑉 2 SIRITORI 定理 QBF は 𝐏𝐒𝐏𝐀𝐂𝐄 完全 も 𝐏𝐒𝐏𝐀𝐂𝐄 完全→ 問9.2 任意の 𝐴 ∈ 𝐏𝐒𝐏𝐀𝐂𝐄 について 𝐴 ≤𝐏m QBF 𝐴 ∈ (𝐍)𝐏𝐒𝐏𝐀𝐂𝐄 を QBF に帰着したい すなわち 与えられた 𝑥 を 先程の漸化式 𝑅 𝑢, 𝑣, 𝑖 + 1 始, から logへの路あり」 𝑉 受, 受 「𝐺𝑀,𝑥𝑅に始 と同値な量化命題論理式 としてから展開 （多項式時間で） ∃ 𝑤 ∈ 𝑉. 𝑅 𝑢, 𝑤, 𝑖 かつ 𝑅 𝑤, 𝑣, 𝑖 をそのまま使って帰納的に展開すると指数長☹ 𝑅 𝑢, 𝑣, 𝑖 + 1 に変換したい そこで ∃ 𝑤 ∈ 𝑉. ∀ 𝑢′ ∈ 𝑉. ∀ 𝑣′ ∈ 𝑉. もし 𝑢′ , 𝑣 ′ = 𝑢, 𝑤 または 𝑤, 𝑣 ならば 𝑅 𝑢′ , 𝑣 ′ , 𝑖 𝐄𝐗𝐏 まとめ 𝐏𝐒𝐏𝐀𝐂𝐄 QBF （= 𝐍𝐏𝐒𝐏𝐀𝐂𝐄） 𝐍𝐏 𝐜𝐨𝐍𝐏 𝐏 未解決 ？ 𝐏 = 𝐏𝐒𝐏𝐀𝐂𝐄 ？ 𝐏𝐒𝐏𝐀𝐂𝐄 = 𝐄𝐗𝐏 但し 少くとも片方は ≠ （𝐏 ≠ 𝐄𝐗𝐏 なので） 連絡 今回 必答問題ナシ（時間があれば前回までのをやって下さい） 採点 先週までの提出分は返却済
© Copyright 2024 ExpyDoc
