演習問題 6 平成 27 年 5 月 25 日第四，五回では多項式時間という制約を課した機械で解ける問題の集まりとして級 P を定義した．今回は NP，また後の回で RP や BPP という級を扱うが，これらは同じく多項式時間限定の機械を用いつつ，その機械と問題との関わりを変えることで定義される． ■補問題今後暫くは判定問題のみを考える．既に取決めたように「○○であるか判定する問題」とは x が○○のとき A(x) = 1，○○でないとき A(x) = 0 という問題 A を指す．この判定問題 A の 1 と 0 を入れ替えた「○○でないか判定する問題」A を A の補問題（complement）という．集合 C に属する問題の補問題の全体を coC で表す．問 6.1 1 C を問題の集合とする．もし C ⊆ coC ならば C = coC となることを示せ．「○○であるか判定」と「○○でないか判定」が異なる問題を指すというのは普段の日本語の感覚に合わないかもしれない．実際，前回扱った P は明らかに補について閉じている（P = coP）ので，両者を区別する必要はあまりなかった．しかし以下ではそうとは限らないので注意せよ．乱択機械前回までは決定性（deterministic）チューリング機械を考えた．すなわち各時点において，各テープの現在の注目点にある記号と機械の内部状態とのみに依存して，次に各テープに何を書込み注目点をいずれの向きに移し内部状態を何にするかが一通りに決るのであった．故に入力字列 x から出力が一通りに決った．機械が（判定）問題 A を解くとは，A の任意の個例 x に対し，この出力字列が正答 A(x) に等しいことをいうのであった．これを拡張して，各時点で次の動きが二通りあり，これを確率 1/2 で選ぶ非決定性（nondeterministic）チューリング機械*1 を考える．つまり決定性機械においては遷移規則が (Q\{q終1 , q終0 })×Γ 1+k 上の函数であったに対し，非決定性機械では (Q\{q終1 , q終0 })× 乱択（randomized）チューリング機械ともいう．なお今回はこの確率的な岐の結果○○となる場合が「あるかどうか」のみを扱う（○○となる確率が高いか低いかは扱わない）ので，上記の「確率 1/2 で」という句は実は要らないのだが，後の回で RP などを扱う際に必要なので既に入れておいた．この「確率 1/2 で」があるとき乱択機械，そうでなく単に岐すると言いたいとき非決定性機械，と世間では何となく言いけているが，本講義では特に区別しないことにする． *1 6-1 Γ 1+k × {0, 1} 上の函数である．一つの入力字列 x に対しても，出力字列は途中の各時点でこの二通りのうちいずれを選んだかに依るので色々ある（とは言ってもここでは判定問題のみを扱い，出力字列が必ず 1 または 0 であるような機械を想定する）．出力のみならず停止するまでの時間もこの岐に依存するが，乱択チューリング機械が多項式時間限定であると言った場合には，或る多項式 p が存在し，どの入力 x に対しても岐によらず p(|x|) 回以内の遷移で停止に至ることを意味するものとする．今回や後の回では，多項式時間限定の乱択機械をい，その出力字列の布と正答 A(x) との関係を指定することにより，NP，RP などの計算量級を定義する．各時点で遷移が二通りあるという代りに，次のごとく乱数を初めに選んでおくと考えても同じことである．すなわち機械に入力，作業，出力テープとは別に「乱数テープ」があり，その注目点は常に右へしか動かないものとする．計算の始まりと同時に乱数テープに無限字列 r が与えられる．r の各ビットは独立に確率 1/2 で 0 または 1 であり，各時点での遷移は，各テープ（乱数テープも含む）の注目点に書かれた記号と機械の内部状態とから一通りに（決定的に）決る．この仕組でも前段落の機械と同じ働きができる（各入力 x に対する出力字列の布は変らない）わけである．またここで r は無限字列としたけれども，入力 x に対する計算時間が例えば多項式 p(|x|) で抑えられていれば，実際には r の初めの p(|x|) 字しかわれない．されば「入力を x とし，遷移先を各時点で確率 1/2 で選ぶ」計算は，「長さ p(|x|) の字列 r を一様に等確率で選んだ上で，入力 x と乱数 r を読み取りながら決定的に進む」計算と同じことである（片方の意味での機械があれば，それと出力字列の布が全く同じであるような，他方の意味での機械が作れる）．そこで以下では議論の都合上このように一定長の乱数を初めに選んでおくという考え方で話を進めることもある． 6-2 級 NP 乱択機械 M が判定問題 A を N 決定*2 するとは，A の各個例 x に対して次が成立つことをいう． • もし A(x) = 1 ならば，入力 x に対し M が 1 を出力する岐がある． • もし A(x) = 0 ならば，入力 x に対し M が 1 を出力する岐はない．多項式時間限定の乱択機械によって N 決定される判定問題の全体を NP で表す．決定性機械は非決定性機械のうち岐しない（各時点での二つの岐が一致する）特殊な場合であることを考えると，明らかに P ⊆ NP である． N 決定の条件が非対称であることに注意せよ．つまり A(x) = 1 のとき M は，乱数 r の値によっては「誤って 0 を出力する」ことがあるが，A(x) = 0 のときに「誤って 1 を出力する」ことはないという，片側誤り（one-sided error）の形になっている．なお N 決定（や後の R 決定）は定義が非対称であるから，冒頭で述べたように問題とその補問題をはっきり区別せねばならない．この定義を少し言換えてみよう．既に述べたように，多項式時間限定の乱択機械 M による計算は，多項式長の乱数列 r を初めに選んでから計算を始める多項式時間限定の決定的な機械 M ′ で代えることができる．この r は乱数テープでなく入力テープに書いてあるとしてもよいから，結局問題 A が NP に属するとは，次を満す多項式 p と多項式時間限定の決定的な機械 M ′ との存在に同値である． • もし A(x) = 1 ならば，或る r ∈ Σ p(|x|) が存在し，入力 (x, r) に対し M ′ が 1 を出力する． • もし A(x) = 0 ならば，そのような r は存在しない．こう考えると字列 r は，個例 x が A(x) = 1 を満すことの「証拠」のごときものといえる．組 (x, r) が与えられたら，この r が証拠として正しいかは M ′ により多項式時間でわかる──但しそのような正しい証拠 r は A(x) = 1 であるときにのみ存在する──というのである．例えば与えられた命題論理式が充足可能か判定する問題 sat（→問 5.4）は NP に属する．この場合，個例 ϕ が充足可能であることの証拠を ϕ の充足割当とすればよい．論理式ϕと字列 r が与えられたとき，r が ϕ を充足する割当であるかは多項式時間で判定できる．その充足割当 r は当然ながら sat(ϕ) = 1 であるときのみ存在する． *2 この「N 決定」や後の回の「R 決定」「BP 決定」は本講義でのみう言い方だが，級の名 NP，RP，BPP は一般的である． 6-3 この定義は，各入力 x に対し，数ある乱数 r のうち少くとも一つが証拠として機械に 1 を出力せしめると述べているに過ぎない．その証拠 r を見出すのは極めて難しいかもしれないから，N 決定ができても実際に判定問題の答を知る役に立つわけではない．ただ世には何かを「見出し」たい状況が多く，それを計算問題として定式化すると NP に属することが多いため，そのような状況を纏めて考える宜のためにこの級を定義するのである． NP は P よりも真に大きく，また coNP とも異なると予想されるが，いずれも証明は得られていない．「NP = coNP ならば P = NP」が成立つか否かもわからない．また NP ∩ coNP = P か否かもわからない．問 6.2 4 与えられた（無向）グラフ G，H に対し，G の部グラフ*3 であって H に同型*4 なものが存在するか判定する問題が NP に属することを示せ．注意上述のように，或る問題が NP に属するという主張は，証拠の適否を判定する機械の存在を意味する．個例 (G, H) に対する証拠 r として何をうのか明確に述べること．問 6.3 2＋13 primes は与えられた正の整数が素数であるか判定する問題である．（1）primes ∈ coNP を示せ（つまり primes ∈ NP を示せ）．（2）primes ∈ NP を示せ．次の事実を証明せずにってよい．正の整数 n が素数であるには，整数 a が存在し，an−1 ≡ 1 (mod n) かつ n − 1 の注意 1 注意 2 各素因数 p に対して a(n−1)/p ̸≡ 1 (mod n) となることが，必要十である．問 6.2 の注意と同じ．入力の整数は二進法で書かれている．なお実は primes ∈ P であることがわかっている*5 ． *3 *4 グラフ (V ′ , E ′ ) が (V, E) の部グラフ（subgraph）であるとは V ′ ⊆ V かつ E ′ ⊆ E なることをいう．下図の二つのグラフは頂点の名づけ方が異なるだけであり，適切に呼び換えれば繋がりの形は同じである．このようなとき両者は同型であるという．つまり二つのグラフ (V1 , E1 )，(V2 , E2 ) が同型（isomorphic）であるとは，或る全単射 ϕ : V1 → V2 が存在し，任意の u，v ∈ V について uv ∈ E1 ⇐⇒ ϕ(u)ϕ(v) ∈ E2 が成立つことをいう． *5 4 A B C D E F 1 2 3 6 5 M. Agrawal, N. Kayal, N. Saxena. PRIMES is in P. Annals of Mathematics 160:781–793, 2004. 6-4