P=NP?問題の解決とNP完全問題の効率的解法に向けて
-
- 西野 哲朗
- 北陸先端科学技術大学院大学情報科学研究科
書誌事項
- タイトル別名
-
- On the P=NP? Question and an efficient Solution of the NP-Complete Problems
この論文をさがす
説明
多くの人々が、P=NP?問題を解くことは非常に難しそうだと感じているが、そのことを数学的に示すことはできないであろうか?そのためのひとつの方法は、現在知られている証明手法が、P=NP?問題を解決するのには弱過ぎることを示すことである。この方針に従った最初の結果を示したのはBaker、GillとSolovayで、彼らは、相対化可能な証明手法ではP=HP?問題は解決できないことを示した。相対化可能な証明手法には、対角線論法やシミュレーションといった当時知られていた主要な証明方法が含まれていたため、研究者は方針変更を余儀なくされた。その後、多くの研究者が非一線回路計算量の研究を始めた。そして1980年代に入ると、組み合わせ論的手法を巧妙に用いて、数多くの相対化不可能な証明手法が発見され、それらの手法を用いて強い下界が示された。
収録刊行物
-
- 電子情報通信学会秋季大会講演論文集
-
電子情報通信学会秋季大会講演論文集 1994 431-432, 1994-09-26
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1571135652413131648
-
- NII論文ID
- 110003339371
-
- NII書誌ID
- AN10398476
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles