2003-09-14 [長年日記]
λ. Re: NP完全問題を解く決定性アルゴリズムについて
私は計算量問題とかにはど素人なので、以下は眉につばを沢山つけて読んでくださいませ。(間違っていたら遠慮せずに突っ込んでもらえると嬉しいです)
まず、構成的数学というのは、直観主義論理に基づいた数学で、要するに証明に背理法*1を使わない世界です。背理法を使えないので、何かが存在することを証明するにも、存在しないことを仮定して矛盾を導いてもダメで、具体的にその何かを構成しないといけないわけです。例えば、ブール式の充足可能性問題(SAT)を解く場合でも、具体的な割り当てを構成する必要があります。つまり、充足可能かという情報だけでなく、実際の割り当てという「それ以上」の情報が必ず分かってしまいます。
そこで、yes/noの答えはP(違ったかも)で求まるけど、そこから「それ以上」の情報を計算するにはより大きな計算量を必要とする、そういう問題とそれを解くアルゴリズムを無理やり捻り出してみて、それを分析中。……というような話だった思います。まだ完成した話ではないそうです。
*1 ここでは「¬Aを仮定して矛盾を導くことで、Aを証明すること」
λ. おでかけ
友人たちと秋葉原と神保町へ。自分から秋葉原に行くなんて、失ってはいけないものを失ってしまったような気もするが、気にしない事にする。それから、秋葉原から神保町まで歩こうとして迷ってしまった。
λ. 読書
- 『グリーン・マイル (1) -- ふたりの少女の死』
- スティーヴン キング (Stephen King) [著], 白石 朗 [訳]
突っ込みは久しぶりです！実は私も昨日秋葉行ったんです！<br>SFC生で自分の知ってる人に2名も会いました（偶然）<br><br>ところで，失ってはいけないものとは？？
私も今日、神保町通りましたよ(だからなんだって訳ではないですが)
問題は秋葉原に行ったかどうかよりも，どんなお店に寄ったか，だと思いますが…
昨日はどうもでした。<br>というか、大事なものを失ってしまうようないかがわしいお店には一切行って無いはずですがー？＾＾；<br><br>アンテナは頑張って書いてください。応援しています。<br>ちょうど、rubyの動くレンタルサーバに引越したところですし（え
sachiさん、有野さん、お久しぶりです。<br>これまで秋葉原や神保町で知り合いに会うことなんてまず無いと思ってましたが、結構ありそうで怖いなぁ (笑)