過去・現在・未来

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 ） 「科学者＋思想家」として見れば、フォン・ノイマンの対極にいたのは、ボームだったように僕には思える。オッペンハイマーの愛弟子であったボームは、「マンハッタン計画」から放逐される。 科学者と思想の問題は、例えば、ニュートンの登場を産業革命を思想的にも準備したと捉えることが可能なように、個別・具体的な「科学者＋思想家」の問題としてだけではなく、より一般的な「科学と時代の思想」というフレームで論ずるべき問題なのだと思う。ただ、そうした視点に立つと、「フォン・ノイマン問題」は厄介な問題になる。 なにか、もってまわった弁解だらけの言い方になってしまった。すこし、切り...