NPにおける不完全問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/28 08:30 UTC 版)
「計算複雑性理論」の記事における「NPにおける不完全問題」の解説
上の問題に関連して、NPクラスに属する問題でPクラスには属しないがNP完全でもない問題は存在するか、という問題もある。つまり、非決定的な多項式時間の解法はあるが、NP完全問題から多項式時間で還元できない問題ということである。このような問題のクラスをNP-intermediate（英語版）と呼び、候補としてグラフ同型問題や整数の因数分解、離散対数問題などがある。もしP ≠ NPが真ならば、そのような問題が存在することが証明されている。
※この「NPにおける不完全問題」の解説は、「計算複雑性理論」の解説の一部です。
「NPにおける不完全問題」を含む「計算複雑性理論」の記事については、「計算複雑性理論」の概要を参照ください。
ウィキペディア小見出し辞書の「NPにおける不完全問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- NPにおける不完全問題のページへのリンク
