NP完全には含まれない問題
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/16 08:14 UTC 版)
「P≠NP予想」の記事における「NP完全には含まれない問題」の解説
NP-(P∪NP完全)となる問題のクラスをNPIとする。P≠NPであれば、NPIは空集合ではないことが示されている。そのような問題の候補としてグラフ同型問題がある。
※この「NP完全には含まれない問題」の解説は、「P≠NP予想」の解説の一部です。
「NP完全には含まれない問題」を含む「P≠NP予想」の記事については、「P≠NP予想」の概要を参照ください。
- NP完全には含まれない問題のページへのリンク