代数化
日本語活用形辞書はプログラムで機械的に活用形や説明を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
代数化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)
集合論的でも自然な証明でもない証明手法として「算術化」と呼ばれるものがある。これは論理式を有限体または有限環上の多項式に置き換えて考察するもので、IP＝PSPACE（Lund,Fortnow,Karloff,Nisan,Shamir(1989)）やMAEXE ⊈ {\displaystyle \not \subseteq } P/poly(Buhrman, Fortnow & Thierauf (1998))、PP ⊈ {\displaystyle \not \subseteq } Size(nk)(Vinodchandran (2005))などの成果を挙げた。ここで、複雑性クラスの分離に用いる際は「算術化された対角線論法」を用いることになる。 ところが、こうした証明方法ではP≠NPを証明不可能であることがAaronson & Wigderson (2009)により示された。彼らは「代数化」という概念を導入し、算術化された集合論的方法によって得られた従来の結果は全て代数化できることを示した。一方、P＝NPとP≠NPは何れも代数化できないことを示した。このため、算術化された集合論的手法による結果は全て代数化できるとすると、この方法ではP＝NPとP≠NPは原理的に証明できないことになる。
※この「代数化」の解説は、「P≠NP予想」の解説の一部です。
「代数化」を含む「P≠NP予想」の記事については、「P≠NP予想」の概要を参照ください。
ウィキペディア小見出し辞書の「代数化」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 代数化のページへのリンク
