On the P=NP? Question and an efficient Solution of the NP-Complete Problems

  • Nishino Tetsuro
    School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku

Bibliographic Information

Other Title
  • P=NP?問題の解決とNP完全問題の効率的解法に向けて

Search this article

Description

多くの人々が、P=NP?問題を解くことは非常に難しそうだと感じているが、そのことを数学的に示すことはできないであろうか?そのためのひとつの方法は、現在知られている証明手法が、P=NP?問題を解決するのには弱過ぎることを示すことである。この方針に従った最初の結果を示したのはBaker、GillとSolovayで、彼らは、相対化可能な証明手法ではP=HP?問題は解決できないことを示した。相対化可能な証明手法には、対角線論法やシミュレーションといった当時知られていた主要な証明方法が含まれていたため、研究者は方針変更を余儀なくされた。その後、多くの研究者が非一線回路計算量の研究を始めた。そして1980年代に入ると、組み合わせ論的手法を巧妙に用いて、数多くの相対化不可能な証明手法が発見され、それらの手法を用いて強い下界が示された。

Journal

Details 詳細情報について

  • CRID
    1571135652413131648
  • NII Article ID
    110003339371
  • NII Book ID
    AN10398476
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top