相対化
相対化
日本語活用形辞書はプログラムで機械的に活用形や説明を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
相対化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)
複雑性クラスを分離するために最初期から主に1970年代末まで利用された証明手法として、集合論の創始者カントールが1891年に考案した対角線論法がある。これは一方のクラスの万能関数であって他方のクラスに属するものを構成し、その対角線部分に着目することで複雑性クラスを分離するもので、P≠EXPTIME(Hartmanis & Stearns (1965))を示す際などに適用された。このような証明手法の特徴として「相対化」と呼ばれる性質の保存がある。複雑性クラス C をオラクル A で相対化するとは、クラスCに属する計算機にオラクル A を付与した新しい複雑性クラス CA を作ることである。ここで、複雑性クラス C,D について対角線論法によって C≠D が示されたとすると、その証明はオラクル A を持つ計算モデルに対しても通用するので、CA≠DA が同時に成り立つ。同様に、対角線論法によって C＝D が示された場合は CA＝DA がどのような A についても成り立つ。 ところが、Baker, Gill & Solovay (1975)は次のことを示した。 PA≠NPA となるオラクル A と、PB＝NPB となるオラクル B が存在する この結果により、対角線論法のように相対化が可能な証明手法では P≠NP を原理的に証明できないことが判明した。
※この「相対化」の解説は、「P≠NP予想」の解説の一部です。
「相対化」を含む「P≠NP予想」の記事については、「P≠NP予想」の概要を参照ください。
ウィキペディア小見出し辞書の「相対化」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 相対化のページへのリンク
