日曜日

センター試験２日目なハズです。外界とのリンクを切断している（ニュースを見ていない）からわからないけど。

ボーっとしていると時間が過ぎるのが早いなぁ。もう月曜日か。ぼちぼち明日提出の計算幾何のレポートをやらなきゃだ。

NP完全問題が一問でも解ければ、「P=NP」になることを証明せよ。

自分的な用語の理解：
P→多項式時間で答えをyes,noで答えられる問題。
NP→答えの証拠が与えられれば、多項式時間でチェックできるyes,noで答えられる問題。
NP完全→多項式時間還元可能なNP問題。
多項式時間還元→あるNP完全問題Aをサブルーチンとして用いることで、そのサブルーチンをO(1)とすれば、NP問題Bが多項式時間で答えをyes,noで答えられること。このときBはAと同程度の複雑さを持っているから、BもNP完全。

昨日図書館に行くまでもなかったなぁ。適当にでっちあげて、はい完成！！