P≠NP予想
複雑性クラスを分離するために最初期から主に1970年代末まで利用された証明手法として、集合論の創始者カントールが1891年に考案した対角線論法がある。これは一方のクラスの万能関数であって他方のクラスに属するものを構成し、その対角線部分に着目することで複雑性クラスを分離するもので、P≠EXPTIME(Hartmanis & Stearns (1965))を示す際などに適用された。このような証明手法の特徴として「相対化」と呼ばれる性質の保存がある。複雑性クラス C をオラクル A で相対化するとは、クラスCに属する計算機にオラクル A を付与した新しい複雑性クラス C を作ることである。ここで、複雑性クラス C,D について対角線論法によって C≠D が示されたとすると、その証明はオラクル A を持つ計算モデルに対しても通用するので、C≠D が同時に成り立つ。同様に、対角線論法によって C=D が示された場合は C=D がどのような A についても成り立つ。
ところが、Baker, Gill & Solovay (1975)は次のことを示した。
P≠NP となるオラクル A と、P=NP となるオラクル B が存在する
この結果により、対角線論法のように相対化が可能な証明手法では P≠NP を原理的に証明できないことが判明した。