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