NP完全問題について

質問

NP完全問題について、最新の研究状況をお教えください。（当方、理系の大学出で、少し概念は学びました）また、今関連のHPやメーリングリストがありましたらお教えください。

回答No.1

siegmund

物理屋の siegmund です．
この方面は素人ですが，最近読みましたのは
「数学七つの未解決問題」(一松信，他，森北出版)です．
この中に，竹内外史先生の解説があります．
文献なども引用されていますので(解説のところ，および巻末)，
そこらへんを手がかりにされてはいかがでしょうか．

余談ですが，2000年5月にクレイ数学研究所
(スーパーコンピューターのクレイ社とは関係ありません)が
数学の七つの未解決問題に対して各々100万ドルの賞金を提供しました．
NP問題はその一つです．
http://www.claymath.org/Millennium_Prize_Problems/
が100万ドル賞金のページです．

お礼

早速の回答ありがとうございます。
もう少し現状に詳しい情報がほしいのですが。
たとえば、？？の補題を解決すれば、解決可能とか？
他の方からの情報を待ちます。