P=NP問題(読み)ぴーえぬぴーもんだい

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

【アルゴリズム】より

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

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

出典|株式会社平凡社「世界大百科事典(旧版)」

ユーラシア大陸、北アメリカ大陸北部に広く分布し、日本では北海道にエゾヒグマが生息する。成獣は体長2メートル以上、体重300キロにもなり、日本最大の陸生動物として知られる。雑食性で草や木の実、サケ、シ...

ヒグマの用語解説を読む