計算機科学の未解決問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
計算機科学の未解決問題（けいさんきかがくのみかいけつもんだい）とは計算機科学における未解決の問題のこと。
目次 |
[編集] 計算複雑性理論
- P≠NP予想
- Pとは多項式時間で解答の見つかる問題のクラスを表し、これに対しNPは多項式時間で解答が検証できる問題のクラスを表す。クラスPの問題は同時にクラスNPであることは証明されている（つまりP⊆NP）。
- ここでP≠NP問題とは、NPがPに含まれるのかどうか（P⊃NPかどうか）、すなわちPとNPは等しいのか（P=NPかどうか）という問題のことである。この問題の解決は、計算機がもつある種の限界を証明することにあたるため、広く注目されている。[1]
- 重要性
- もしPとNPが同じクラスであれば（つまりP=NPであれば）、素因数分解や充足可能性問題など現在効率的な算法の存在しない問題を解くことができる。
- 現在の予想
- P≠NP予想という名前も示すとおり、現在PとNPは異なるクラスであろうと予想されているが、証明されていない。
[編集] 暗号理論
一方向性関数は存在するか？
- 詳細
- 一方向性関数とは順方向への計算は容易だが、逆方向への計算が困難な関数のこと。つまり「一方向性関数が存在するかどうか？」とは「暗号化は容易だが、復号は困難であるような暗号化方法は存在するのか？」という問題を一般化したもの。 容易、困難という言葉の定義は数学的に厳密に与えられている。現在、一部の研究者達は離散対数とinverting RSA暗号の計算アルゴリズムは一方向性関数だろうと予測している。[2]
- 重要性
- もし一方向性関数が存在しない場合、公開鍵暗号は不可能である。 逆に一方向性関数が存在するならば、その存在は多くの複雑性のクラスの問題がlearnableではないこと、またP≠NPであることを示す。
- 現在の予想
- 存在するだろうとは予想されているが、証明されていない。
[編集] ハイ・パフォーマンス・コンピューティング
計算機はどこまでスピードアップできるか？
- 詳細
- 理論的には加速定理が示すように、どんな計算も任意の速度で行うことが可能である。しかしそのような計算速度を得るための具体的な実現方法は存在しない。 そのためスカラープロセッサ, グリッド・コンピューティング、 分散コンピューティングなどの様々なアーキテクチャに対して、それぞれ技術的な利点と限界を知る必要がある。
- 重要性
- 計算の速度は、計算機で扱える問題の種類とその限界を規定する。
- 現在の予想
- 計算速度の問題に対する部分的な解答としてアムダールの法則がある。
クラスターに参加できるノード数は、どこまで増やせるか?
- 詳細
- クラスターに参加するコンピューターの数が増えていくにつれて、うまく動作しないコンピューターの出てくる可能性は増加する。 そうなると うまく動作しないコンピューター、すなわち不良ノード、が発生する平均の間隔であるmean time between failuresは当然短くなってくる。この時間が不良ノードの回復に要する時間、または不良ノードを点検する平均時間より短くなってしまう場合が問題となる。この場合より高い計算能力を得るには、使用するアルゴリズムまたは使用するアーキテクチャを変更するしかない。
このように動作不良の平均確率が高い場合には、その平均確率がクラスター全体の計算能力の限界を決めてしまう。
- 重要性
- クラスターのサイズに制約がある場合、当然 全体としての計算能力はそのサイズによって制約をうける。そのためどれだけ多くのコンピューターが参加できるのかは、全体としての計算能力を高めるためには避けて通れない問題となる。
[編集] 参考文献
- ↑ S. A. Cook and Leonid Levin Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151--158
- ↑ W.Diffie, M.E.Hellman IEEE Trans. Inform. Theory, IT-22, 6, 1976, pp.644-654 オンラインコピー (HTML)
| 未解決問題の一覧 | |
| 分野別 | 数学上の未解決問題 - 物理学の未解決問題 - 生物学上の未解決問題 - 計算機科学の未解決問題 |
| その他 | 懸賞金問題 |
