自然な証明
自然な証明の概念はアレクサンダー・ラズボロフ(英語版)とステーブン・ルディッチ(英語版)が1994年に発表し、論文は1997年に出版された。この業績により両者は2007年のゲーデル賞を受賞した。
自然な証明が対象とするのは、ブール関数の回路計算量の下界の証明である。 自然な証明は、直接または間接に、ブール関数が何らかの「自然な組合せ論的な性質」を持つことを示し、その性質を用いて複雑性クラスを分解する。ところが、ラズボロフとルディッチは「擬似乱数生成器が指数的な複雑性を持つ」と仮定した状況下で、そうした方法ではある種の複雑性クラスを分離できないことを示した。特に、擬似乱数生成器の存在を仮定すると、こうした証明方法では複雑性クラスPとNPを分離できない。
論文中では次のように説明している。
「(前略)P≠NPを証明するための典型的な証明戦略を考えてみよう。 まず、ブール関数または関連するポリトープや他の構造などの値の「ディスクレパンシー」や「散乱」や「変動」などと言った数学的概念を何かしら定式化する。(中略) 次に、帰納的な推論を通じて、多項式サイズの回路では「低い」ディスクレパンシーを持つ関数しか計算できないことを示す。(中略) 最後に、SATか何かのNP問題が「高い」ディスクレパンシーを持つことを示して、P≠NPであると結論する。
我々の4節の主定理は、以上のような証明戦略は決してうまく行かないという証拠を与える」
ラズボロフとルディッチの定義に依れば、ブール関数が持つ何らかの性質が「構成的」と「広い」という二つの条件を満たすとき、その性質は「自然」であると言う。