計算機科学の未解決問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/08/13 06:09 UTC 版)
計算機科学の未解決問題（けいさんきかがくのみかいけつもんだい）とは計算機科学における未解決の問題のこと。
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であることを示す。現在、存在するだろうとは予想されているが、証明されていない。
計算機の速度限界
理論的には加速定理が示すように、どんな計算も任意の速度で行うことが可能である。しかしそのような計算速度を得るための万能な具体的な実現方法は存在しない。そのため各計算に対して、理論的には各種の計算モデル、あるいは実際的には各種のコンピュータ・アーキテクチャに対して、具体的な加速法、あるいは限界などといったものを知る、ということは一群の研究テーマである。
問題の並列性と計算機の並列性にもとづいた計算機の高性能化に関する法則のひとつに、アムダールの法則がある。
クラスターの参加ノード数限界
クラスターに参加するコンピューターの数が増えていくにつれて、うまく動作しないコンピューターの出てくる可能性は増加する。そうなると うまく動作しないコンピューター、すなわち不良ノード、が発生する平均の間隔である平均故障間隔（MTBF）は当然短くなってくる。この時間が不良ノードの回復に要する時間、または不良ノードを点検する平均時間より短くなってしまう場合が問題となる。この場合より高い計算能力を得るには、使用するアルゴリズムまたは使用するアーキテクチャを変更するしかない。このように動作不良の平均確率が高い場合には、その平均確率がクラスター全体の計算能力の限界を決めてしまう。
もしクラスターのサイズに制約がある場合、当然 全体としての計算能力はそのサイズによって制約をうける。そのためどれだけ多くのコンピューターが参加できるのかは、全体としての計算能力を高めるためには避けて通れない問題となる。
近年解決した問題
 | この節の加筆が望まれています。 |
参考文献
- ^ 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)
- 計算機科学の未解決問題のページへのリンク
