複雑性理論と人工知能技術（３） ナッシュとゲーデル

1950年代に入ると、時代の先鋭な知性たちは、今日の複雑性理論の原型とも言える認識に到達し始める。

スコット・アーロンソンは、複雑性理論の到達点を概観した論文 "N = NP?"  https://goo.gl/TZUkgh の冒頭に、ジョン・ナッシュの 1955年のNSA（スノーデンがいた、あのSNAだ！）宛の手紙をあげている。かつては「機密文書」とされていて、いつかの時点で情報公開されたものらしい。

誰にも破れない暗号を作るためには、指数関数的な計算が必要な暗号を作ればいいことを述べている。また、そうすれば、それまでの職人技的な暗号破り（多分、チューリングやファインマンがしていたこと）は「過去」のものになると、明確に自覚している！

-----------------
　現時点での、私の一般的な予想は次のようなものです。：
ほとんどすべての十分に複雑なタイプの暗号化にとって、特に、鍵の異なる部分によって与えられた命令が、相互に複雑に相互作用して、それが暗号化の最終的な決定において影響を与えている場合、鍵の計算の平均的な長さは、鍵の長さ、すなわち、鍵の持つ情報の内容に関して、指数関数的に増加します。

　もし、この予想が正しいと仮定すれば、この一般的な予想の重要性を理解するのは容易です。それは、実際的には誰も破れない暗号を設計することを、極めて簡単に実行できることを意味します。暗号が洗練されたものになるにつれて、熟練したチームなどによる暗号破りのゲームは、「過去」のものになっていくはずです。

　この予想の性質は、たとえ特別な種類の暗号をとっても、私にはそれを証明できないようなものです。また、私は、それが証明されることも期待していません。」

-----------------
https://www.nsa.gov/news-features/declassified-documents/nash-letters/assets/files/nash_letters1.pdf

現文は、こちら。

僕は、ナッシュのNSAへの手紙は知らなかったのだが、有名なのは、1956年にゲーデルが、フォン・ノイマンに宛てた、次の手紙である。ゲーデルが、ほとんど完全に、問題の所在を把握していることがわかる。

-----------------
我々が、一階の述語論理の全ての式Fに対して、全ての自然数について、長さn（長さ=記号の数）のFの証明があるかどうかを決定することを可能にするチューリング機械を、簡単に構築することができるのは明らかです。

機械がこれを決定するのに必要とするステップの数をψ(F, n)とし、[特定のFについて] φ(n)=maxψ(F, n)としましょう。問題は、最適なマシンで、φ(n)がどのくらい急速に大きなものになるかです。

我々は、 [nとは独立な定数Kについて] φ(n) ≥ K・n  であることを示すことができます。[ φ(n)は、nの一次式より大きいということ。]　実際に、実行時間が Knに比例する（またはKn^2に比例する）マシンが実際にあったとした場合 [「論理式Fに対して長さnのFの証明があるかどうか？」という問題が、nの一次式または二次式に比例する時間で解けるなら]  、これは最大級に重要な結果をもたらすことになります。

つまり、「決定問題」の解決不可能性にもかかわらず、YesかNoかの質問に答えるタイプの問題の場合、数学者の知的努力は完全に機械に置き換えることが可能であることを、明確に示すことができるでしょう。

我々が　実際に行うべきことは、単純に数nを選ぶだけです。そのnが非常に大きくても、もしも、マシンが [「長さnのFの証明があるかどうか？]という質問に ] "No"という結果を出した場合には、さらに問題を考える理由はなくなります。
-----------------
https://rjlipton.wordpress.com/the-gdel-letter/

もっとも、これらの50年代半ばの認識は、広く共有されたものではなかったかもしれない。（論文として公開されたものではなく「手紙」だった！）

現在のようなスタイルで、N = NP? 問題を最初に定式化したのは、バークレーのStephen Cookだという。1967年のことだ。