N**Pクラスの階層とMIP*=RE定理
前回、次のような、二つの対をなす複雑性のクラスを三つほど見てきた。
1. NP \(O(3^n)\)の証明時間
P \(O(n)\)の検証時間
2. NEXP \(O(3^{2^n})\)の証明時間
EXP \(O(2^n)\)の検証時間
3. NEEXP \(O(3^{2^{2^n}})\)の証明時間
EEXP \(O(2^{2^n})\)の検証時間
一つ確認しておきたいのは、2番目の NEXPクラスは、NPクラスではないということである。NPクラスは、証明のの検証が多項式時間で終わるクラスのことだが、このNEXPクラスは、検証に指数関数的時間を要するクラスである。多項式時間では、このクラスの検証は終わらない。
同様に、3番目のNEEXPクラスは、NPクラスでもNEXPクラスでもない。それは、証明の検証に、はるかに長い時間を必要とする、それらよりずっと複雑なクラスである。
形から見れば、NP, NEXP, NEEXP, ...という延長上に、NEEEXPなり NEEEEXP ... といった複雑性クラスを考えることができそうである。また、それは、大きな認識の飛躍のようにも思えないかもしれない。
結果的には、確かにそうなのだが、そうしたアイデアは複雑性理論の中で、最初から「自然」に生まれたものではないことには注意が必要である。そのことは、複雑性理論の歴史を振り返ればわかる。
歴史的には、1番目の NPクラスとNP-完全の概念の定式化は、1971年の CookとLevinに遡る。この間紹介してきた「グラフの3色塗り分け問題」がNP-完全であることを示したのはKarpで1972年のことだ。1970年代初頭は、複雑性理論の創世記である。
2番目のNEXPクラスの特徴づけがなされ、その基本的な性質が解明されたのは、BabaiとFortnowとLundが、NEXP = MIP を証明した時である。MIPはMulti-Prover Interactive Proof である。1991年のことだ。1990年代、Interactive Proofの手法の導入によって、複雑性理論は新しい段階に入る。
3番目のNEEXPクラスの特徴づけをあたえたのは、Anand Natarajan と John Wrightである。彼らは、BabaiとFortnowとLundが、NEXPの特徴付けに利用したMIPを、エンタングルメントで拡張した MIP* というInteractive Proofの新しい枠組みを使って、 NEEXP ⊆ MIP* を証明した。 2019年、つい一年半前のことである。
要するに、NPからNEXPに至るのに 20年、NEXPからNEEXPに至るのに、約30年の時間を要したということだ。
ただ、NatarajanとWrightのNEEXP ⊆ MIP* の証明の後、その手法を応用して、我々の複雑性の認識は、急展開することになる。
2020年、Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen [JNVWY]らは、MIP*=RE定理の証明の中で、次のことを証明する。
NEEEXP ⊆ MIP*
NEEEEXP ⊆ MIP*
NEEEEEXP ⊆ MIP*
NEEEEEEXP ⊆ MIP*
・・・
・・・
RE ⊆ MIP*
こうして、MIP*という枠組みの中で、我々は、NP, NEXP, NEEXP, NEEEXP, NEEEEXP, ... と無限に続く複雑性クラスの階層をキチンと理解することができるようになった。無限に続くと言ったが、それは正確ではないかもしれない。Eの並びは、2の肩に乗っかる2の冪乗（Conwayのchain表記を使えば、2 → (2 → (2 → 2) ...)の並びで表現される巨大だが有限な数に対応している。
NPからNEEXPに進むまでに50年の歴史が必要だったのだが、いまや、我々は、この複雑性の階層を瞬時に一望できるのだ。MIP*=RE定理は、複雑性理論に革命をもたらした。
NEXP -> NEEXPに30年かかっていること、右側では、90年代以降では、証明手法として、Interactive Proofが大きな役割を果たしていることに、注目してほしい。
コメント
コメントを投稿