P=NP問題（読み）ぴーえぬぴーもんだい

世界大百科事典（旧版）内のP=NP問題の言及

【アルゴリズム】より

…〈ハミルトン閉路の存在判定〉の決定性計算量は，これまでに知られている最良のアルゴリズムでも都市数nの指数関数になる。しかし巧妙なアルゴリズムによって〈決定性計算量をnの多項式でおさえることはできないだろうか〉という問題(P＝NP問題と同値)は，おそらく無理であろうと予測されながら未だに解決されていない，理論的コンピューター科学の大問題である。
[関連領域]
　アルゴリズムに関連して，次のような研究が行われている。…

※「P=NP問題」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社「世界大百科事典（旧版）」