自然な証明

計算複雑性理論において、自然証明とは、ある計算複雑性クラスが別の計算複雑性クラスと異なることを証明するある種の証明である。これらの証明はある意味で「自然」であるが、（疑似乱数関数の存在に関する広く信じられている予想を仮定すると）そのような証明はP対NP問題を解くのに用いることは不可能であることが示される。

概要

自然証明の概念は、アレクサンダー・ラズボロフとスティーブン・ルディッチが1994年に発表した論文「自然証明」で導入され、後に1997年に出版され、2007年のゲーデル賞を受賞した。[ 1 ]

具体的には、自然証明はブール関数の回路複雑度の下限を証明します。自然証明は、ブール関数が特定の自然な組み合わせ特性を持つことを直接的または間接的に示します。ラズボロフとルディッチは、彼らの主定理で規定されているように「指数困難」な擬似乱数関数が存在するという仮定の下、これらの証明は特定の複雑性クラスを分離できないことを示しています。特に、擬似乱数関数が存在すると仮定した場合、これらの証明は複雑性クラスPとNPを分離できません。[ 2 ]

たとえば、彼らの記事にはこう書かれています。

[...] P≠NPを証明するための一般的に考えられている証明戦略を考えてみましょう。
  • ブール関数の値、または関連する多面体やその他の構造の「矛盾」や「散布」や「変動」という数学的な概念を定式化します。[...]
  • 多項式サイズの回路では「低い」矛盾の関数しか計算できないことを帰納的議論によって示してください。[...]
  • 次に、 SAT、または NP の他の関数に「高い」矛盾があることを示します。
第4節の主要定理は、このような証明戦略は決して成功しないという証拠を示しています。[ 3 ]

ブール関数の性質は、ラズボロフとルディッチによって定義された構成性条件と大小条件を満たす性質を含む場合、自然であると定義されます。大まかに言えば、構成性条件とは、 n入力ブール関数の2 nサイズの真理値表を入力として与えた際に、n の増加に伴って漸近的に、性質が（準）多項式時間で決定可能であることを必要とします。これは、 nの単指数時間と同じです。理解しやすい性質は、この条件を満たす可能性が高いです。大小条件とは、すべてのブール関数の集合のうち十分に大きな部分に対して、その性質が成り立つことを必要とします。

ある性質が複雑性クラスCに対して有用であるとは、その性質を持つブール関数の列のすべてが、Cの外側の言語を無限回定義する場合を言う。自然証明とは、ある言語がCの外側に存在することを証明する証明であり、 Cに対して有用な自然性質を指す。

ラズボロフとルディッチは、P/polyよりも小さいクラスCに対する下限証明のうち、「自然化」、すなわち自然な証明に変換可能なものの例をいくつか挙げている。重要な例として、パリティ問題がAC 0クラスに存在しないことの証明が挙げられる。彼らは、これらの証明で用いられる手法を拡張してより強い下限を示すことはできないという強力な証拠を示している。特に、AC 0の自然証明はAC 0 [m]に対しては役に立たない。

ラズボロフとルディッチは、離散対数問題の指数下限を自然証明では証明できないというアヴィ・ウィグダーソンの無条件証明も再現しています。

この論文のメカニズムは、定数深さ、多項式サイズの閾値回路の計算量クラスTC 0に対する下限証明を実際に阻害するという強い信念が現在ある。この計算量クラスTC 0はP/polyより小さいと考えられているが、証明されていない。 [ 4 ]この信念は、特定の楕円曲線群における因数分解の困難性に関する広く信じられている予想の下では、TC 0で計算可能な指数的に困難な擬似乱数関数が存在するためである。[ 5 ]しかし、一部の研究者は、ラズボロフ・ルディッチの制限は、指数空間における困難性や完全性など、「超自然的な」下限証明が何を含むかについての良い指針となると考えている。[ 6 ]

注記

  1. ^ 「ACM-SIGACT 2007 Gödel Prize」 。 2016年3月3日時点のオリジナルよりアーカイブ。2014年8月11日閲覧。
  2. ^ AA RazborovとS. Rudich (1997). 「自然証明」 . Journal of Computer and System Sciences . 55 : 24–35 . doi : 10.1006/jcss.1997.1494 .（下書き）
  3. ^ラズボロフ+ルディッチ (1997)、p.26 左
  4. ^ 「Complexity Zoo:T - Complexity Zoo」。
  5. ^ Naor, Moni; Reingold, Omer (2004). 「効率的な擬似乱数関数の数論的構築」 . Journal of the ACM . 51 (2): 231– 262. doi : 10.1145/972639.972643 . S2CID 8665271 . 
  6. ^ K. Regan (2002年10月). 「P vs. NPに対するMulmuley-Sohoniアプローチの理解」(PDF) .欧州理論計算機科学協会紀要. 78 : 86–97 .

参考文献

「 https://en.wikipedia.org/w/index.php?title=Natural_proof&oldid=1324114140」より取得