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