証明の試みと難しさ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)
P≠NP予想の面白さと難しさは、複雑性クラスを分離するために利用・考案されてきた様々な証明手法が、証明手法自体の本質的な限界によりP≠NPを証明できないという、不可能性の証明がこれまで幾度も得られてきた点にある。つまり、時代が進めば進むほど証明の可能性が原理的に狭められてきた。だからと言ってP＝NPの方が確からしいと傾いた訳でもなく、新たな証明手法が必要だと考えられてきた点がまた特徴的である。以下にあらましを述べる。本節は主に岡本 (2009)の解説記事に基づく。
※この「証明の試みと難しさ」の解説は、「P≠NP予想」の解説の一部です。
「証明の試みと難しさ」を含む「P≠NP予想」の記事については、「P≠NP予想」の概要を参照ください。
ウィキペディア小見出し辞書の「証明の試みと難しさ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 証明の試みと難しさのページへのリンク
