自然な証明

ウィキペディア

自然な証明

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/06/07 18:16 UTC 版)

計算複雑性理論において、自然な証明（英：natural proof）とは、ある複雑性クラスが他の複雑性クラスとは異なることを示すための証明手法の一種である。これに則る証明はある意味で「自然」だが、擬似乱数生成器の存在を仮定すると、そのような方法ではP≠NP予想を解決不可能であることが言える。なお「擬似乱数生成器が存在する」という主張は広く正しいと信じられている予想である。

概要

自然な証明の概念はアレクサンダー・ラズボロフとステーブン・ルディッチが1994年に発表し、論文は1997年に出版された。この業績により両者は2007年のゲーデル賞を受賞した。

自然な証明が対象とするのは、ブール関数の回路計算量の下界の証明である。 自然な証明は、直接または間接に、ブール関数がある「自然な組合せ論的な性質」を持つことを示す。ラズボロフとルディッチは論文中で、「擬似乱数生成器が指数的な複雑性を持つ」と仮定した状況下で、これらの方法ではある種の複雑性クラスを分解できないことを示した。特に、擬似乱数生成器の存在を仮定すると、こうした証明方法では複雑性クラスPとNPを区別できない。

例えば、論文中に次の記述がある。

「（前略）P≠NPを証明するための典型的な証明戦略を考えてみよう。

• まず、ブール関数または関連するポリトープや他の構造物などの値の「矛盾」や「散乱」や「変化」などと言った数学的概念を何かしら定式化する。
• 次に、帰納的な推論を通じて、多項式サイズの回路では「低い」矛盾を持つ関数しか計算できないことを示す。（中略）
• 最後に、充足可能性問題(SAT)か何かのNP問題が「高い」矛盾を持つことを示して、P≠NPであると結論する。

我々が4節の主定理で示すのは、以上のような証明戦略は決してうまく行かないという証拠である」

ラズボロフとルディッチの定義に依れば、ブール関数が持つ何らかの性質が「構成的」と「広い」という二つの条件を満たすとき、その性質は「自然」であると言う。「構成的」とは、おおまかに言えばn-変数ブール関数の大きさ2ⁿの真理値表を入力とした時に、その性質が成り立つかどうかがn が増大するにつれて漸近的に（準）多項式時間で判定できることを指す。これは時間がn の指数関数になることと同じである。人間に理解できるような性質は概ねこの条件を満たすと考えてよいだろう。「広い」とは、全てのn-変数ブール関数の全体2²ⁿ個の中で、その性質を満たす関数の割合が2^-O(n)以上であることを指す。

ある性質がまた次の条件を満たすとき、その性質は複雑性クラスCに対して「有用」であると言う。その条件とは、その性質を持つ全てのブール関数について、それが複雑性クラスCには属さないことを証明できることである。以上を纏めて「自然な証明」とは、Cに対して有用かつ自然な性質を見出すことにより、何かしらの問題がCに属さないことを示すという証明または証明方針のことである。

多項式サイズの回路の集合が計算できる問題のクラスをP/polyと呼ぶ。P/polyはPを包含することが知られているので、P/poly≠NPが言えれば直ちにP≠NPが従う。 ラズボロフとルディッチは、P/polyよりも小さな複雑性クラスCに対する回路計算量の既知の下界証明を多数例示し、それらが悉く「自然化」できること、つまり自然な証明に変換できることを示した。重要な例としてはパリティ問題がクラスAC⁰に属さないことの証明がある。彼らはその上で、これらの証明で使われた技法を拡張する方向では更に強い下界を示すことはできないという強い証拠を与えた。特に、AC⁰-自然な証明はAC⁰[m]に対して有用とはなり得ない。

ラズボロフとルディッチはまた、Avi Wigdersonによる「自然な証明では離散対数問題の指数的な下界を証明できない」という証明を再現した。

証明のあらまし

自然な証明の限界に関する証明のあらましを示す。以下は岡本 (2009, p. 23)の紹介記事を更に簡略化しているので、厳密ではない。

「擬似乱数生成器が存在する」ことと「性質C_nを用いた自然な証明により、多項式サイズの回路の集合Sの下界が示された」ことを仮定し、背理法を用いる。

まず、擬似乱数生成器の存在より、擬似ランダム関数F_nを構成できることが言える。擬似ランダム関数とは、直感的には十分ランダムに見える出力を返す関数であり、真のランダム関数との間で両者を識別するような多項式時間のアルゴリズムが存在しないものを指す。F_nは多項式サイズの回路で計算できるので、性質C_nが「有用」であることにより、F_nは性質C_nを持たない。 一方、真のランダム関数R_nは定義より集合Sに含まれず、性質C_nが「広い」ことにより、一定以上の確率で性質C_nを持つ。性質C_nはまた「構成的」なので、F_nおよびR_nが性質C_nを持つかを判定する効率的な（Nの多項式時間の）アルゴリズムD_Nが存在する。従ってD_NでF_nを判定すると結果は常に「性質C_nを持たない」となり、R_nを判定すると一定以上の確率で「性質C_nを持つ」ことが判る。これはある意味で擬似ランダム関数を破っている。これを用いて暗号分野の標準的な手法を適用すると、更に翻ってF_nの構成に用いた擬似乱数生成器が破られることに繋がり、「擬似乱数生成器が存在する」という仮定と矛盾する。

ところが、この仮定を棄却することは難しい。例えば「素因数分解の困難性」などの暗号分野の基礎を成す仮定から容易に導出できるからである。このためもう一つの仮定である「性質C_nを用いた自然な証明により、多項式サイズの回路の集合Sの下界が示された」が棄却されることになる。

その他

TC⁰は定数深さで多項式サイズを持つ閾値回路で計算可能な問題の複雑性クラスである。これはP/polyよりも小さいと広く信じられているが、下界は未だに証明されていない。現在ではこちらも「自然な証明」が障害になっていると考えられている。何故なら、ある種の楕円関数の族の因数分解に関する困難性を仮定すると（これは広く信じられている）、TC⁰の中に指数的に困難な擬似ランダム関数(en)が存在するからである。 しかしながら一部の研究者は、ラズボロフ＝ルディッチの制限はありうべき「超自然的な」下界証明を示唆する、寧ろよい目安だと考えている。例えば指数領域困難や同完全な性質などである。

参考文献

• 岡本, 龍明 (2009-12-01), “相対化,自然な証明,代数化／P≠NP予想の難しさ”, 数学セミナー (日本評論社) 48 (12): 20-25 
• 天野, 一幸 (2010年2月1日). “自然な証明 (PDF)”. 電子情報通信学会. pp. 25-26. 2017年6月7日閲覧。
• A. A. Razborov (2004). “Feasible Proofs and Computations: Partnership and Fusion”. Proceedings of the 31st ICALP. Lecture Notes in Computer Science. 3142. pp. 8-14.  (Draft)
• Lance Fortnow (2006年5月10日). “The Importance of Natural Proofs”. 2017年6月7日閲覧。
• Chow, Timothy Y. (2011年). “WHAT IS... a Natural Proof?”. AMS. 2014年8月5日閲覧。

ウィキペディア小見出し辞書

自然な証明

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)

「P≠NP予想」の記事における「自然な証明」の解説

詳細は「自然な証明」を参照 1980年代に入り、集合論的手法ではない回路計算量に着目する新しい証明手法が開発された。これは今日「自然な証明」と呼ばれるもので、AC0≠NC1（Furst, Saxe & Sipser (1984)）やmP/poly≠NP（Razborov (1985))などの成果を挙げた。この手法からP≠NPを見る場合は、Pを包含するクラスP/poly（英語版）に着目してP/poly≠NPを証明することが問題となる（そこから直ちにP≠NPが従う）。 ところが、当初の期待にも関わらず、P/poly≠NPに向けた進展はぱったり止まってしまい、やがて研究者の間で何か原因があるのではないかと議論されるようになった。そんな中、Razborov & Rudich (1997)はその原因を突き止め、次のことを示した。 素因数分解の困難性を仮定すると、自然な証明ではP/poly≠NPを証明できない 「自然な証明」は名前の通り自然な発想に基づく証明戦略であり、それまで得られた複雑性クラスの分離に関する殆ど全ての証明で利用されていた。ところが、そうした証明手法ではP≠NPを原理的に証明できないことが判明したのである。RazborovとRudichはこの成果により2007年のゲーデル賞を受賞した。但し彼らが定義した「自然な証明」には幾つか技術的な条件があることから、この条件を巧妙に回避することで障害を乗り越えようとする研究方向も存在する。