arxiv に P≠NP 問題を解決した論文が投稿される fromage曰く、計算機科学の未解決問題であるP≠NP予想を解決したとする論文がarxivに投稿された（結城浩氏のツイート、論文のページ）。NP完全問題は、巡回セールスマン問題のような、入力（重み付きグラフと閾値）に対する証拠（巡回経路）があれば入力を多項式時間で判定できる問題の中では最も難しいものである。NP完...

arxiv に P≠NP 問題を解決した論文が投稿される
=======================================

arxiv に P≠NP 問題を解決した論文が投稿される

fromage曰く、計算機科学の未解決問題であるP≠NP予想を解決したとする論文がarxivに投稿された（結城浩氏のツイート、論文のページ）。NP完全問題は、巡回セールスマン問題のような、入力（重み付きグラフと閾値）に対する証拠（巡回経路）があれば入力を多項式時間で判定できる問題の中では最も難しいものである。NP完...

http://ift.tt/1abnmbU
August 16, 2017 at 08:15PM