計算量演習 第八回 平成 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
© Copyright 2025 ExpyDoc