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年代に入ると、組み合わせ論的手法を巧妙に用いて、数多くの相対化不可能な証明手法が発見され、それらの手法を用いて強い下界が示された。

収録刊行物

詳細情報 詳細情報について

  • CRID
    1571135652413131648
  • NII論文ID
    110003339371
  • NII書誌ID
    AN10398476
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ