計算量演習第八回

計算量演習
第八回
平成 27 年 1 月 16 日
A
問 8.1
B
問 8.2 次の各命題について，
（A）成立，
（B）不成立，
（C）P = NP と同値，
（D）NP = coNP
「授業評価アンケート」に回答して下さい（無記名）．
と同値，のいずれかを答えよ．理由は不要．但し P = NP や NP = coNP の成否が判らな
いと確かめられない選択肢を答えた場合は，正しいかもしれないが不正解とする．
（1）sat ∈ P．
（2）sat ∈ NP．
（3）sat ∈ coNP．
（4）幾つかの非負整数 a1 ，…，an と非負整数 B とが（二進法で）与えられたとき，集合
S ⊆ {1, . . . , n} であって和
が，P に属する．
!
ai が丁度 B になるものが存在するか判定する問題
i∈S
（5）（4）の問題を解く擬多項式時間算法が存在する．即ち入力中の各非負整数 m が二進
法でなく
字列 0m によって表されていれば P に属する．
（6）（4）の「存在するか判定する」の代りに「存在するときにはそれを求める」とした
探索問題を考える．この問題に対する多項式時間算法が存在する．
（7）NP ⊆ PSPACE．
（8）P = PH．
（9）PNP = PcoNP ．
（10）L = PSPACE．
8-1
C
問 8.3
0
お疲れさまでした。特に C を少しでも解いた人はかなり手応えがあったかと思い
ます。計算量（やその他の理論
野の研究）に興味を持った方、最先端の論
を読んだり、
何か研究をしてみませんか。講義や演習でどの話題が面白かったかなど一言添えて河村ま
で連絡下さい（[email protected] 七号館 205）。
締切（普段よりも早いので注意）
A
1 月 16 日（金）二限終了時
B
1 月 20 日（火）（事務室印有効）
8-2

Download Report