他の問題との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)
NP完全 1971年にスティーブン・クックが定式化した概念で、クラスNPに属し、クラスNPに属する他の全問題が多項式時間帰着される問題をNP完全という。充足可能性問題をはじめとして、数千個以上の問題がNP完全であることが示されている。これらのNP完全問題の一つでもクラスPに属することを示せれば、P＝NPとなる。 NP完全には含まれない問題 NP-(P∪NP完全)となる問題のクラスをNPIとする。P≠NPであれば、NPIは空集合ではないことが示されている。そのような問題の候補としてグラフ同型問題がある。 coNP NP問題の補問題からなるクラスをcoNPという。NP≠coNPならば、P≠NPとなることが示されている。
※この「他の問題との関係」の解説は、「P≠NP予想」の解説の一部です。
「他の問題との関係」を含む「P≠NP予想」の記事については、「P≠NP予想」の概要を参照ください。
ウィキペディア小見出し辞書の「他の問題との関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
このページでは「ウィキペディア小見出し辞書」から他の問題との関係を検索した結果を表示しています。
Weblioに収録されているすべての辞書から他の問題との関係を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から他の問題との関係を検索
Weblioに収録されているすべての辞書から他の問題との関係を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から他の問題との関係を検索 - 他の問題との関係のページへのリンク
