自然な証明
「構成的」とは、おおまかに言えばn-変数ブール関数の大きさ2の真理値表を入力とした時に、その性質が成り立つかどうかがn が増大するにつれて漸近的に(準)多項式時間で判定できることを指す。これは時間がn の指数関数になることと同じである。人間に理解できるような性質は概ねこの条件を満たすと考えてよいだろう。「広い」とは、全てのn-変数ブール関数の全体2個の中で、その性質を満たす関数の割合が2以上であることを指す。
ある性質がまた次の条件を満たすとき、その性質は複雑性クラスCに対して「有用」であると言う。その条件とは、その性質を持つ全てのブール関数について、それが複雑性クラスCには属さないことを証明できることである。以上を纏めて「自然な証明」とは、Cに対して有用かつ自然な性質を見出すことにより、何かしらの問題がCに属さないことを示すという証明または証明方針のことである。
多項式サイズの回路の集合が計算できる問題のクラスをP/poly(英語版)と呼ぶ。P/polyはPを包含することが知られているので、P/poly≠NPが言えれば直ちにP≠NPが従う。 ラズボロフとルディッチは、P/polyよりも小さな複雑性クラスCに対する回路計算量の既知の下界証明を多数例示し、それらが悉く「自然化」できること、つまり自然な証明に変換できることを示した。重要な例としてはパリティ問題がクラスACに属さないことの証明がある。彼らはその上で、これらの証明で使われた技法を拡張する方向では更に強い下界を示すことはできないという強い証拠を与えた。特に、AC-自然な証明はAC[m]に対して有用とはなり得ない。
ラズボロフとルディッチはまた、Avi Wigdersonが仮定なしで示した「自然な証明では離散対数問題の指数的な下界を証明できない」という証明を再現した。