関連記事
3SAT問題を多項式時間で解くアルゴリズムが発表される。P=NP証明に？
2011年1月24日 22:32
記事提供元：スラド
あるAnonymous Coward 曰く、
本家/.によると、Vladimir Romanov氏が、3SAT問題を解く多項式時間アルゴリズムなるものをリリースしたそうだ（該当のブログエントリ） 。
3SAT問題はNP完全なので、この主張が正しければ、P=NPであることになる。ソースコードはGitHubにて公開されている 。
NP完全問題と3SAT問題の関連については東京電機大学坂本直志准教授の講義資料などが参考になる。
スラッシュドットのコメントを読む | 数学 | サイエンス
関連ストーリー：
ミツバチはコンピュータよりも速く巡回セールスマン問題を解ける 2010年10月26日
P!=NP 予想、証明されるか ? 2010年08月09日
粘菌が組み合せ最適化問題を解く 2008年04月14日
※この記事はスラドから提供を受けて配信しています。
スポンサードリンク
