non deterministic polynomial timeと呼ぶ。これはNPとあらわされる。

NP完全：非決定性の計算モデルにより多項式ステップで解け、さらに非決定性の計算モデルによって解く限りではどうしても多項式ステップが必要な問題をNP完全と呼ぶ。

NP完全問題は、それを解くのに必要な計算量の下限が存在する問題である。

PとNPとが等しいかそうでないかは、計算数学の未開決問題になっている。仮にあるNP完全問題がPで解けることを示すか、解けないことを示せれば、この未解決問題は決着する。現在まで、多数のNP完全問題が見つかっているが、Pで解くアルゴリズムはみつかっていない。もちろん、Pで解けないことも証明されていないが、NP完全問題は多項式ステップでは解けないのではないかと予想されている。

これらの概念はチューリング・マシンを計算モデルとしても定義することができる。

暗号問題

超高速計算機のひとつの重要な応用課題は、暗号解読である。暗号技術はネットワーク社会となり、いわゆる公開かぎの利用が普及することに伴い、情報化社会の中核技術の一つとして浮上してきた。この技術の計算上の問題は、ある与えられた大きな数を素数の積に分解することである。これを素因数分解という。

素因数分解問題以外にも、計算機能を要求する数学的な問題は沢山ある。こうした問題への挑戦において、超高速計算機にその性能を発揮させるためには、効率のよい解法Algorithmを探すとともに、それを実行させるためのプログラムにも工夫を凝らさなければならない。

6.5  情報と通信

・シャノンの通信理論

・情報理論の真価

・通信理論：符号論と暗号

Sampling理論:AnalogからDigitalへ

　情報時代と言われる今日、我々の身近な情報の多くがディジタル形式で扱われるようになった。文字フォント、音楽、放送、カメラなどもディジタル化が進行している。これら