関連記事
arxivに「P≠NP」問題解決した論文が投稿
記事提供元:スラド
fromage曰く、 計算機科学の未解決問題であるP≠NP予想を解決したとする論文がarxivに投稿された(結城浩氏のツイート、論文のページ)。
NP完全問題は、巡回セールスマン問題のような、入力(重み付きグラフと閾値)に対する証拠(巡回経路)があれば入力を多項式時間で判定できる問題の中では最も難しいものである。NP完全問題を多項式時間で解くアルゴリズムはまだ見つかっていない。そのようなアルゴリズムが存在すればP=NPであり、存在しないならばP≠NPであるが、現在までどちらなのか分かっていない。
今回投稿された論文では、P≠NP(つまり、NP完全問題は多項式時間で解けない)と結論付けている。著者が計算機科学の専門家(大学の情報科学科の教授)である点から、この論文に期待する意見もある。しかし、arxivには査読の仕組みがないため、この証明が正しいかどうかは、現段階では不明である。
ところで、P≠NP問題を解決したと主張する論文のリストを示しているページによると、(査読を通ったものを含めて)116本の論文がこれまで発表されている。
スラドのコメントを読む | サイエンスセクション | 数学
関連ストーリー:
ケプラー予想の証明が完了 2014年08月15日
難問「ABC予想」解明か 2012年09月19日
3SAT問題を多項式時間で解くアルゴリズムが発表される。P=NP証明に? 2011年01月24日
P!=NP 予想、証明されるか ? 2010年08月09日
リーマン予想解決される? 2004年06月10日
※この記事はスラドから提供を受けて配信しています。
スポンサードリンク