ソフトウェア工学四方山話
ソフトウェアと関って36年、ソフトウェア工学と連れ立って32年.その成立時から見てきたソフトウェア工学に関連することを、気ままな感じで思いつくまま述べてみる
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 件のコメント:
コメントを投稿
次の投稿
前の投稿
ホーム
登録:
コメントの投稿 (Atom)
自己紹介
TNakajima
詳細プロフィールを表示
ブログ アーカイブ
►
2019
(1)
►
12月
(1)
►
2016
(2)
►
4月
(2)
►
2015
(4)
►
6月
(2)
►
5月
(2)
►
2014
(1)
►
10月
(1)
►
2012
(3)
►
4月
(1)
►
3月
(2)
▼
2011
(7)
►
12月
(1)
►
4月
(3)
▼
1月
(3)
NP完全問題と3SAT問題 P=NP証明?
Selected Papers on Fun and Games
音声検索 Chromeエクステンション『Voice Search』
►
2010
(56)
►
12月
(3)
►
10月
(2)
►
9月
(1)
►
8月
(2)
►
7月
(9)
►
6月
(6)
►
5月
(4)
►
4月
(2)
►
3月
(7)
►
2月
(6)
►
1月
(14)
►
2009
(31)
►
12月
(9)
►
11月
(9)
►
10月
(13)
►
2008
(12)
►
5月
(1)
►
2月
(4)
►
1月
(7)
0 件のコメント:
コメントを投稿