計算理論(試験準備)

NPの中でも一番難しい問題を作ろうとしてNP完全問題という概念が生まれたが,実はNPな問題の多くはNP完全であることがわかってきた.

クラスNPの問題を多項式時間で還元してNP完全にすれば良いのでクラスNPの問題は全てNP完全な気がしますけど,証明はされてないっぽい.

NP完全な問題の1例として,3SAT問題が挙げられる.

HAMPATH問題もNPに属することを説明したが,実はNP完全.

試験解説

今日は試験の解説が主でした.

以下の形式で問題を出す.

好きな言語を指定し,それを受理するTuring機械の状態遷移図を示せ.

NP完全問題の例を1つ挙げよ.問題を説明し,例を挙げること,NP完全問題であることを証明する必要はない.

持ち込みシートには表裏書いていいということなので,私の場合A4表裏に印刷することになります.私はB4ではなくA4を使うことになりますが,印刷して良いというアドバンテージを認めてもらっているのでこれぐらいは問題ないですね.

持ち込みシートは提出して,裏は半分レポートのような形で提出することになるそうです.

このエントリーをはてなブックマークに追加 fb-like g-plusone pocket