P≠NP予想
集合論的でも自然な証明でもない証明手法として「算術化」と呼ばれるものがある。これは論理式を有限体または有限環上の多項式に置き換えて考察するもので、IP=PSPACE(Lund,Fortnow,Karloff,Nisan,Shamir(1989))やMAEXP ⊈ {\displaystyle \not \subseteq } P/poly(Buhrman, Fortnow & Thierauf (1998))、PP ⊈ {\displaystyle \not \subseteq } Size(n)(Vinodchandran (2005))などの成果を挙げた。ここで、複雑性クラスの分離に用いる際は「算術化された対角線論法」を用いることになる。
ところが、こうした証明方法ではP≠NPを証明不可能であることがAaronson & Wigderson (2009)により示された。彼らは「代数化」という概念を導入し、算術化された集合論的方法によって得られた従来の結果は全て代数化できることを示した。一方、P=NPとP≠NPは何れも代数化できないことを示した。このため、算術化された集合論的手法による結果は全て代数化できるとすると、この方法ではP=NPとP≠NPは原理的に証明できないことになる。