- チューリングは、人間が客観的な手順で行う情報処理は、チューリング機械により代行できると主張。また、ヒルベルトのいう決定問題には、一般的な解法が存在しないことがあり得ることを証明。例えば、①不定方程式の解の存在を判定する一般的な方法は存在しない（第10問題）、②ある言語で書かれたプログラムに、あるデータを与えたとき、そのプログラムが有限時間内に停止するか否かを判定するプログラムは、その言語で書くことはできない（停止問題）。
- ある特定のチューリング機械で、どんなチューリング機械の動作をも忠実に再現できるものがある（万能チューリング機械）。
- 線形計画法は、古くからEXPに属することは知られていたが、1979年にカチアンが新しいアルゴリズムを発表し、Pに属することが判明。
- 非決定性アルゴリズムでは、決定問題に対し、①非決定論的（Non-deterministic）な選択を許す、つまり、幾つかの操作から一つを選ぶところで、どんな条件でどれを選ぶかを指定せず、ランダムに選ばせる、②計算量は、最も運がよい場合で数える、③答えがNOの場合は無視してよい。（一定回数の試行で終了）
- NPクラスの問題は、非決定性アルゴリズムで、多項式時間（Polynomial time）で解ける。PがNPに含まれるのは確実。NPでかつPではない問題は、一つも見つかっていない。
- ある問題QがNP完全であるとは、①QはクラスNPに属している、②クラスNPに属しているどんな問題Xのどんな具体例αも、ある一般的な手順で問題Qのある具体例βに翻訳でき、その翻訳の手順はαのサイズの多項式時間で抑えられ、しかもαに対する答えがYESかNOかは、βに対する答えがYESかNOかに必ず一致する。
- P＝NPであるための必要十分条件は、あるNP完全な問題Qが、クラスPに属していることである。
