計算機科学の未解決問題

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であることを示す。現在、存在するだろうとは予想されているが、証明されていない。

理論的には加速定理が示すように、どんな計算も任意の速度で行うことが可能である。しかしそのような計算速度を得るための万能な具体的な実現方法は存在しない。そのため各計算に対して、理論的には各種の計算モデル、あるいは実際的には各種のコンピュータ・アーキテクチャに対して、具体的な加速法、あるいは限界などといったものを知る、ということは一群の研究テーマである。

問題の並列性と計算機の並列性にもとづいた計算機の高性能化に関する法則のひとつに、アムダールの法則がある。