わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

2007-08-16から1日間の記事一覧

P=NP問題を理解するためのステップ〜おしまい(強引に)

P=NPとは? P≠NPとは? 前回紹介した二つの集合PとNPですが,属する要素が全く同じなら,P=NPです. 「P⊂NP」(任意の問題pに対して,p∈Pならばp∈NP)と「NP⊂P」(任意の問題pに対して,p∈NPならばp∈P)の両方が成り立つことと等価です. ただし,前者の包含関係は…