arxivに「P≠NP」問題解決した論文が投稿
2017年8月17日 08:13
fromage曰く、 計算機科学の未解決問題であるP≠NP予想を解決したとする論文がarxivに投稿された（結城浩氏のツイート、論文のページ）。
NP完全問題は、巡回セールスマン問題のような、入力（重み付きグラフと閾値）に対する証拠（巡回経路）があれば入力を多項式時間で判定できる問題の中では最も難しいものである。NP完全問題を多項式時間で解くアルゴリズムはまだ見つかっていない。そのようなアルゴリズムが存在すればP＝NPであり、存在しないならばP≠NPであるが、現在までどちらなのか分かっていない。
今回投稿された論文では、P≠NP（つまり、NP完全問題は多項式時間で解けない）と結論付けている。著者が計算機科学の専門家（大学の情報科学科の教授）である点から、この論文に期待する意見もある。しかし、arxivには査読の仕組みがないため、この証明が正しいかどうかは、現段階では不明である。
ところで、P≠NP問題を解決したと主張する論文のリストを示しているページによると、（査読を通ったものを含めて）116本の論文がこれまで発表されている。