過去・現在・未来

Interactive proofs and the hardness of approximating cliques https://dl.acm.org/doi/pdf/10.1145/226643.226652 The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP languages is constructed, where the verifier uses very few random bits and communication bits. Last, the connection between cliques and efficient multi-prover interaction proofs, is shown to yield hardness results on the complexity of approximating the size of the largest clique in a graph. Why is maximum clique often easy in practice? http://www.optimization-online.org/DB_FILE/2018/07/6710.pdf To this day, the maximum clique problem remains a computationally challenging problem. Indeed, despite researchers’ best efforts, there exist unsolved benchmark instances with one thousand vertices. However, relatively simple algorithms solve real-life

【宇宙の終わりと黒色矮星】 図のようなストーリーで、「宇宙の終わりとエントロピー」という投稿を準備していたのだが、いろいろ雑念が湧いて気がすすまなくなる。その理由は別稿で。 この図は、「閉じられた部屋でのガスの拡散」というわかりやすいモデルで理解されるエントロピーの増大の法則が、あるフェーズから、宇宙規模でみれば、「全ての物質のブラックホールへの吸収・収斂」として現れると言うことを主張している。最初、ペンローズのこの話を読んだときには、目からウロコだった。 このストーリーにはもっと先がある。最近のシミュレーションでは、指数関数的に膨張する宇宙では、巨大なブラックホールに捕捉されるのは、宇宙全体の物質の10%程度だという。恒星起源のブラックホールは 10^67 年で、銀河系中心の巨大ブラックホールも 10^99年で、ホーキング放射で「蒸発」し姿を消す。 ブラックホールに捕捉されなかった宇宙の残りの90%の物質は、元それが属した銀河系から孤立したまま星の一生の進化を続ける。太陽の1.2倍程度の質量を持つ星は「白色矮星」になるのだが、「白色矮星」は 10^17年で「黒色矮星」に変わる。 「黒色矮星」は、現代の「宇宙の終末論」では、もっとも注目されている天体なのだが、それはまだ観測されていないと言う。というのも、この天体は光を出さないからだ。「黒色矮星」の中心は、最も安定な原子である鉄の「結晶」でできていて、温度は絶対零度近くに冷却されている。 「黒色矮星」は、とても長生きする天体である。陽子崩壊がおきるなら、黒色矮星の寿命は 10^32年程度だが、もし陽子が安定しているとすれば、太陽の 1.24倍程度の質量を持つ「黒色矮星」は、10^1600年後に突然崩壊して超新星爆発を起こす。もっと軽い、太陽の1.16倍程度の質量を持つ「黒色矮星」は、10^32000 年後（！）に超新星爆発を起こす。 このシナリオによれば、宇宙は、とてつもなく長い長い退屈な時間をかけて、その死を迎える。「黒色矮星」の超新星爆発は、宇宙の死を飾る最後の打ち上げ花火である。その後には、宇宙には何も起こらない。 この記事は、ジョン・バエズの "Black Dwarf Supernovae" を基にしたものだ。https://johncarlosbaez.wordpress.com/202

【宇宙が膨張していることの意味】 宇宙が膨張していることは、多くの人は知っていると思う。ただ、それがどういう意味を持つのかについては、僕はあまり考えたことがなかった。 今年4月に、Toby Ordが "The Edges of Our Universe" （「我々の宇宙の端」とでも訳せばいいのかな）https://arxiv.org/pdf/2104.01191.pdf 論文のAbstract は、こう述べる。 「この論文は、我々が観測または影響を与えうる宇宙がどれくらいあるかについて、基本的な因果関係の限界を考察したものだ。この論文では、次の四つの基本的な領域を区別している。すなわち、影響を与えうる宇宙、観測可能な宇宙、因果的には観測可能な宇宙、究極的には観測可能な宇宙の四つである。ついで、この論文は、これらの（そしてその他の）因果的な限界が、宇宙間の文明が非常に長い未来にわたって達成可能なものに、どのような物理的制限を課すかについて示す。」 宇宙が猛烈なスピードで膨張しているということは、我々が現在、光で観測している「宇宙の端っこ」が、どんどん我々から遠ざかり我々の視界から消えていくことを意味する。100万年後には、現在観測可能な銀河の 0.02%が視界から消える。 この程度は理解できるかもしれない。ただ、もっと先がある。1千万年後には、銀河の0.2%が消え、一億年後には、銀河の2%が消えると言う。10億年後には20%、100億年後には80%、そして、1500億年後には、なんと、99.9999997% の銀河が、我々の視界から失われる！ これは興味深い。事実だろう。我々は、宇宙の膨張とともに、宇宙の中で孤立してゆくのだ。 一転して、この論文の第二部は、こうしたビジョンの「恒星間文明への応用」についてである。SFネタにはことかかない。基本的には、宇宙の歴史は「結合の時代」と「孤立化の時代」に区分されるので、「恒星間文明」が成立するにはタイミングが重要だと言う話だと思う。 SF好きな人におすすめである。 この論文が論じている1500億年後を待たずとも、「わずか」38億年後に、我々の「天の川銀河」は、となりの「アンドロメダ銀河」に衝突する。その後の宇宙の運命については、ジョン・バエズの次の記事が面白い。（僕は、Toby Ordの論文を、バエズのブロ

【Turing's Cathedral】 スモーリンの"Einstein's Unfinished Revolution" にダイソンがエンドースを寄せてた。そのタイトルが面白そうだったので読み始める。タイトルは、"Turing's Cathedral" （スモーリンの本が出た時、僕が書いたブログは、こちら。" Bohmian Rapsody "  https://maruyama097.blogspot.com/2019/05/bohmian-rhapsody.html ) 読み始めてすぐに間違いに気づく。この本の著者は、僕が知っている 物理学者のダイソン(Freeman Dyson)ではなく、別のダイソン(Ggeorge Dyson)だった。もっとも、著者のGeorge DysonはFreeman Dysonの息子さんだった。 同じような間違いをしたことがある。チッパラとともに、Deep Specificationのムーブメントの中心人物の一人は、アッペルだったのだが、僕は、このアッペルをしばらくのあいだ、「四色問題」をコンピュータで解いた、アッペル＝ハーケンのアッペルだと思っていた。Deep Specification のアッペル（Andrew Appel）は、「四色問題」のアッペル(Kenneth Appel )の、息子さんだった。 ちなみに、"Q is for Quantum" を書いた、Terry Rudolphは、シュレジンガーのお孫さんだという。 話を、"Turing's Cathedral" に戻そう。 この本は、チューリングについての本ではなかった。フォン・ノイマンについての本だ。1947年から1951年にかけて、当時プリンストンにいたフォン・ノイマンは、MANIACというコンピュータを作り上げるプロジェクトを主導する。 フォン・ノイマンが作ったこのIAS( I nstitute for  A dvanced  S tudy) ＝プリンストン) 製のコンピュータが、どのような動機で開発されたか、また、それがその後のコンピュータ技術の発展に大きな役割を果たしたことを詳述したものだ。 （"MANIAC"

【ボームと外村 彰 】 以前、スモーリンの本を読んで、ボームのことが気にかかっていた。といっても、あまりきちんと追いかけていなかった。（「 Bohmian Rhapsody 」https://maruyama097.blogspot.com/2019/05/bohmian-rhapsody.html ） 去年は、ずっと「対話型証明」を追いかけていて、「対話」の意味にについて考えさせられたのだが、そこでまた、ボームの「対話論」に出会うことになる。 対話の意味について、なにか自分で「哲学的」なことを書こうとすると、僕の形式主義的で要素還元論的なアプローチだけではうまくはいかない。といっても、先のブログでも書いたのだが、僕はボームに対して、特にかつての彼の「ホーリズム（全体論）的」な思想に対して、すこし反発があった。 今は、物理学や計算科学の初頭的な解説を始めているのだが、そこでは、20世紀の科学の巨人としてのフォン・ノイマンの仕事を避けて通るわけにはいかない。でも、「思想家」としてのフォン・ノイマンは、恐るべき（多分、貧困で非人間的）存在だ。 ダイソンが、"Turing's Cathedral" でフォン・ノイマンについて書いた、「人類が発明した、最も破壊的なものと最も建設的なものが、正確に同じ時期に現れたのは、偶然ではない。」というフレーズは、科学者とその思想は、簡単には分離できないと言うことを意味している。（「 Turing's Cathedral 」https://maruyama097.blogspot.com/2021/04/turings-cathedral.html ） 「科学者＋思想家」として見れば、フォン・ノイマンの対極にいたのは、ボームだったように僕には思える。オッペンハイマーの愛弟子であったボームは、「マンハッタン計画」から放逐される。 科学者と思想の問題は、例えば、ニュートンの登場を産業革命を思想的にも準備したと捉えることが可能なように、個別・具体的な「科学者＋思想家」の問題としてだけではなく、より一般的な「科学と時代の思想」というフレームで論ずるべき問題なのだと思う。ただ、そうした視点に立つと、「フォン・ノイマン問題」は厄介な問題になる。 なにか、もってまわった弁解だらけの言い方になってしまった。すこし、切り

【正しいコードを正しく書くこと】 接触確認アプリ「COCOA」の不具合についての 調査報告書 を読んだ。少し、暗い気持ちになる。 不具合についての経過はこうだ。主に、二つの段階があった。 第一。「1.1.3 バージョン以前」 陽性者と「単なる接触」があっただけで通知が出てしまう不具合があった。 この不具合は、昨年8月ごろには、すぐに気づかれていた。なぜなら「市役所や企業で大量通知が発生して、保健所検査負担が増加する一方、ほとんど陽性者は出ないということで、大きな問題という認識」は生まれていた。 第二。「1.1.4 バージョンアップ」 主要に、先の問題に対処しようとして行われた、「1.1.4 バージョンアップ」で、Android端末上のCOCOAで大きな問題が発生する。Androidでは、濃厚接触に該当するケースでも、 必要な通知・表示まで、一切、出なくなってしまったのだ。 Android では、４つのパラメーターで算出されるリスク値の設定のミスで、濃厚接触を示す値が論理的に生じ得ない状況となっていたからである。悪いことに、その不具合に、4ヶ月もの間、誰も気づかなかった。（GitHub上では、指摘があったにもかかわらず） 二つの不具合を振り返ってみれば、「接触確認アプリ」の中核的な機能である「濃厚接触の有無のチェック」に重大なバグがあったことがわかる。 大量通知を乱発したは、1.1.3 バージョン以前のアプリは、「接触確認」についていえば、10年前にAndroid界隈ではやったすれ違い通信「すれちがったー」レベルのものだし、二つ目の1.1.4 バージョンのどんなに濃厚接触しても濃厚接触なしと答えるのは、「接触確認アプリ」としては最悪である。 こうしたバグは、テストをしないと見つからないものなのだろうか？　僕は、そうは思わない。もちろん、テストすることに反対しているわけではないのだが、今回のミスは、ちゃんと情報を集めて、ちゃんと考えれば気づくことのできた誤りだと思う。 実際に手を動かして当該部分のコードを書いた人には、きつい言い方になるかもしれないが、プログラマーは、どんな状況にあっても、正しいコードを正しく書くことを求められていると、僕は思う。 当面の僕の主要な関心は、ストレートで狭いもので、どうしてプログラマーがミスを犯したか、どうしてマネージャーがそれに気がつかな

【 MIP*=REの含意 】 [ ゲーデルの不完全性定理とMIP*=RE定理 ] 「MIP*=RE定理」というのは、MIP*という複雑性のクラスが、「決定不能」だということを述べている定理です。それは、ゲーデルの「不完全性定理」に端を発する、一連の「決定不能」型定理の一つと考えることが出来ます。 ゲーデルの結果は、人間の認識可能性の一つの限界を示すものとして、多くの人にいわば認識論的・哲学的なレベルで衝撃を与えました。 ただ、その方法の適用は、数学の基礎の理論の内側にとどまっていて、科学の方法論そのものに影響を与えることはなかったし、ゲーデルの定理が、他の数理科学の分野の問題解決に応用されたことはなかったように思います。 21世紀の「不完全性定理」とも呼ぶべき「MIP*=RE定理」は、この点では、明らかに様相が異なります。 それは、新興科学としての「コンピュータ・サイエンス」の「決定不能」型定理として登場したのですが、その定理は、狭い意味での 「コンピュータ・サイエンス」の枠を超え、純粋数学や物理学の基礎理論に、重要な応用を持つのです。 エンタングルしたnonlocalゲームの値の「決定不能」性は、量子力学の基礎の「ティレルソンの問題」に対する否定的な答えを導きます。また、この結果は、数学の作用素環論の長年の難問だった「コンヌの埋め込み予想」否定的に解決しました。  [ 計算可能性理論と計算複雑性理論の接するところ「拡大されたCHテーゼ」の誤り] 計算複雑性理論は、計算可能性理論の達成を受けて、決定可能なもの（計算可能なもの）にフォーカスを合わせて、その現実的な計算の「手に負えなさ」の階層を研究することを課題としてきました。 MIP*=RE の左辺MIP*は複雑性のクラスで、右辺はREは、計算可能性理論の基本的カテゴリーです。 理論的には、計算可能性理論の枠組みの中でも、原理的には計算可能でも、いくらでも計算リソースを必要とする計算が存在することはよく知られていました。だからこそ計算複雑性理論が生まれたのですが。 ただ、計算可能性を「多項式時間」での計算可能性に制限することが当たり前のようになっていきます。これを「拡大されたチャーチ・チューリングのテーゼ」というのですが、それは間違ったものだと、思います。 [ 決定論的な認識と確率論的な認識] 証明へのInt