2011年1月25日火曜日

NP完全問題と3SAT問題 P=NP証明?

3SAT問題を多項式時間で解くアルゴリズムが発表される。
P=NP証明に?
hylomによる 2011年01月24日 22時32分の掲載
Vladimir Romanov氏が、3SAT問題を解く多項式時間アルゴリズムなるものをリリースしたそうだ(該当のブログエントリ)3SAT問題はNP完全なので、この主張が正しければ、P=NPであることになる。ソースコードはGitHubにて公開されている 。

0 件のコメント: