|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 計 ： [けい] 1. (n,n-suf) plan ・ 計算 ： [けいさん] 1. (n,vs) (1) calculation 2. reckoning 3. count 4. (2) forecast ・ 計算機 ： [けいさんき] 【名詞】 1. computer 2. calculator ・ 機 ： [き, はた] (n) loom ・ 科 ： [か] 1. (n,n-suf) department 2. section ・ 科学 ： [かがく] 【名詞】 1. science ・ 学 ： [がく] 【名詞】 1. learning 2. scholarship 3. erudition 4. knowledge ・ 未 ： [ひつじ, み, いま（だ）] 【名詞】 1. not yet ・ 未解決 ： [みかいけつ] 1. (adj-na,n) unsettled 2. pending 3. unresolved ・ 未解決問題 ： [みかいけつもんだい] (n) unresolved problem ・ 解決 ： [かいけつ] 1. (n,vs) settlement 2. solution 3. resolution ・ 決 ： [けつ] 【名詞】 1. decision 2. vote ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
計算機科学の未解決問題（けいさんきかがくのみかいけつもんだい）とは計算機科学における未解決の問題のこと。 == P≠NP予想 == Pとは多項式時間で解答の見つかる問題のクラスを表し、これに対しNPは多項式時間で解答が検証できる問題のクラスを表す。クラスPの問題は同時にクラスNPであることは証明されている（つまりP⊆NP）。 ここでP≠NP問題とは、NPがPに含まれるのかどうか（P⊃NPかどうか）、すなわちPとNPは等しいのか（P=NPかどうか）という問題のことである。この問題の解決は、計算機がもつある種の限界を証明することにあたるため、広く注目されている。〔S. A. Cook and Leonid Levin ''Proceedings of the 3rd Annual ACM Symposium on Theory of Computing'' (1971), pp. 151--158〕 もしPとNPが同じクラスであれば（つまりP=NPであれば）、素因数分解や充足可能性問題など現在効率的な算法の存在しない問題を解くことができる。P≠NP予想という名前も示すとおり、現在PとNPは異なるクラスであろうと予想されているが、証明されていない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「計算機科学の未解決問題」の詳細全文を読む スポンサード リンク
|