グラフ同型性判定問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/12/03 16:15 UTC 版)
与えられた二つのグラフが同型か否かを判定する問題である。この問題がNPに属することは分かっているが、P, co-NP, BPPに属するかどうかは分かっていない。NP完全に属するかどうかも分かっていないので、量子計算機を用いて多項式時間で解けるかどうかに関しても、さかんに研究されている。
※この「グラフ同型性判定問題」の解説は、「グラフ同型」の解説の一部です。
「グラフ同型性判定問題」を含む「グラフ同型」の記事については、「グラフ同型」の概要を参照ください。
ウィキペディア小見出し辞書の「グラフ同型性判定問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- グラフ同型性判定問題のページへのリンク
