自然な証明
計算複雑性理論において、自然な証明（英：natural proof）とは、ある複雑性クラスが他の複雑性クラスとは異なることを示すための証明手法の一種である。これに則る証明はある意味で「自然」だが、擬似乱数生成器の存在を仮定すると、そのような方法ではP≠NP予想を解決不可能であることが言える。なお「擬似乱数生成器が存在する」という主張は広く正しいと信じられている予想である。
概要
自然な証明の概念はアレクサンダー・ラズボロフとステーブン・ルディッチが1994年に発表し、論文は1997年に出版された。この業績により両者は2007年のゲーデル賞を受賞した[1]。
自然な証明が対象とするのは、ブール関数の回路計算量の下界の証明である。 自然な証明は、直接または間接に、ブール関数が何らかの「自然な組合せ論的な性質」を持つことを示し、その性質を用いて複雑性クラスを分解する。ところが、ラズボロフとルディッチは「擬似乱数生成器が指数的な複雑性を持つ」と仮定した状況下で、そうした方法ではある種の複雑性クラスを分離できないことを示した。特に、擬似乱数生成器の存在を仮定すると、こうした証明方法では複雑性クラスPとNPを分離できない[2]。
論文中では次のように説明している。
- 「（前略）P≠NPを証明するための典型的な証明戦略を考えてみよう。
- 我々の4節の主定理は、以上のような証明戦略は決してうまく行かないという証拠を与える」
ラズボロフとルディッチの定義に依れば、ブール関数が持つ何らかの性質が「構成的」と「広い」という二つの条件を満たすとき、その性質は「自然」であると言う。「構成的」とは、おおまかに言えばn-変数ブール関数の大きさ2nの真理値表を入力とした時に、その性質が成り立つかどうかがn が増大するにつれて漸近的に（準）多項式時間で判定できることを指す。これは時間がn の指数関数になることと同じである。人間に理解できるような性質は概ねこの条件を満たすと考えてよいだろう。「広い」とは、全てのn-変数ブール関数の全体22n個の中で、その性質を満たす関数の割合が2-O(n)以上であることを指す。
ある性質がまた次の条件を満たすとき、その性質は複雑性クラスCに対して「有用」であると言う。その条件とは、その性質を持つ全てのブール関数について、それが複雑性クラスCには属さないことを証明できることである。以上を纏めて「自然な証明」とは、Cに対して有用かつ自然な性質を見出すことにより、何かしらの問題がCに属さないことを示すという証明または証明方針のことである。
多項式サイズの回路の集合が計算できる問題のクラスをP/polyと呼ぶ。P/polyはPを包含することが知られているので、P/poly≠NPが言えれば直ちにP≠NPが従う。 ラズボロフとルディッチは、P/polyよりも小さな複雑性クラスCに対する回路計算量の既知の下界証明を多数例示し、それらが悉く「自然化」できること、つまり自然な証明に変換できることを示した。重要な例としてはパリティ問題がクラスAC0に属さないことの証明がある。彼らはその上で、これらの証明で使われた技法を拡張する方向では更に強い下界を示すことはできないという強い証拠を与えた。特に、AC0-自然な証明はAC0[m]に対して有用とはなり得ない。
ラズボロフとルディッチはまた、Avi Wigdersonが仮定なしで示した「自然な証明では離散対数問題の指数的な下界を証明できない」という証明を再現した。
証明のあらまし
自然な証明の限界に関する証明のあらましを示す。以下は岡本 (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の限界が示された」が棄却されることになる。
その他
TC0は定数深さで多項式サイズを持つ閾値回路で計算可能な問題の複雑性クラスである[3]。これはP/polyよりも小さいと広く信じられているが、下界は未だに証明されていない。現在ではこちらも「自然な証明」が障害になっていると考えられている。何故なら、ある種の楕円関数の族の因数分解に関する困難性を仮定すると（これは広く信じられている）、TC0の中に指数的に困難な擬似ランダム関数(en)が存在するからである。しかしながら、一部の研究者はラズボロフ＝ルディッチの制限は寧ろ良い指針だと信じており、（訳注：「自然な」証明が駄目ならば、それに代わる）「超自然な」下界証明に用いるべき道具の目安だと考えている。そうした道具の候補としては例えば指数領域困難や同完全な性質などがある[4]。
脚注
- ^ “ACM-SIGACT 2007 Godel Prize” (2007年). 2017年6月7日閲覧。
- ^ Razborov, A. A.; Rudich, S. (1997). “Natural proofs”. Journal of Computer and System Sciences 55: 24-35. doi:10.1006/jcss.1997.1494. (Draft)
- ^ https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T#tc0
- ^ Regan, K. (2002-10). “Understanding the Mulmuley-Sohoni Approach to P vs. NP” (PDF). Bulletin of the European Association for Theoretical Computer Science 78: 86-97.
参考文献
- 岡本, 龍明 (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日閲覧。