証明のあらまし
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/06/07 18:16 UTC 版)
自然な証明の限界に関する証明のあらましを示す。以下は岡本 (2009, p. 23)の紹介記事を更に簡略化しているので、厳密ではない。 「擬似乱数生成器が存在する」ことと「性質Cnを用いた自然な証明により、多項式サイズの回路の集合Sの下界が示された」ことを仮定し、背理法を用いる。 まず、擬似乱数生成器の存在より、擬似ランダム関数Fnを構成できることが言える。擬似ランダム関数とは、直感的には十分ランダムに見える出力を返す関数であり、真のランダム関数との間で両者を識別するような多項式時間のアルゴリズムが存在しないものを指す。Fnは多項式サイズの回路で計算できるので、性質Cnが「有用」であることにより、Fnは性質Cnを持たない。 一方、真のランダム関数Rnは定義より集合Sに含まれず、性質Cnが「広い」ことにより、一定以上の確率で性質Cnを持つ。性質Cnはまた「構成的」なので、FnおよびRnが性質Cnを持つかを判定する効率的な（Nの多項式時間の）アルゴリズムDNが存在する。従ってDNでFnを判定すると結果は常に「性質Cnを持たない」となり、Rnを判定すると一定以上の確率で「性質Cnを持つ」ことが判る。これはある意味で擬似ランダム関数を破っている。これを用いて暗号分野の標準的な手法を適用すると、更に翻ってFnの構成に用いた擬似乱数生成器が破られることに繋がり、「擬似乱数生成器が存在する」という仮定と矛盾する。 ところが、この仮定を棄却することは難しい。例えば「素因数分解の困難性」などの暗号分野の基礎を成す仮定から容易に導出できるからである。このためもう一つの仮定である「性質Cnを用いた自然な証明により、多項式サイズの回路の集合Sの下界が示された」が棄却されることになる。
※この「証明のあらまし」の解説は、「自然な証明」の解説の一部です。
「証明のあらまし」を含む「自然な証明」の記事については、「自然な証明」の概要を参照ください。
- 証明のあらましのページへのリンク
