« 学会誌編集委員会 | トップページ | 粉粒体の論文(続報) »

2005/06/19

Nature 論文: 一般制限問題の解の存在

Nature 6/9号に、一般制限問題の解の存否が、相転移として扱えて、相転移点が厳密に評価できるという論文が掲載されていた(N&V, 論文本体)。要するに0か1をとる変数がk個あるとして、それらの間の制限(つまり、関係式)がいくつになったら「解がなくなるか」という問題。答えは大体2kln 2くらいだそうである。つまり、とてつもなくたくさん制限条件が無い限り、解はある、ということらしい。普通はもっと条件が厳しいような気もする。
この様なことは本当はnMDSでも考えるべきなんだろう。N個の点をD次元の空間に埋め込むとき、あらかじめ与えられた距離の大小関係に従うように点を埋め込め、という問題である。この場合、N個の点の間の距離はN(N-1)/2個ある。これをある順番で並べるのだから大きさが隣り合った距離同士の大小関係でいいのだから、制限条件はN(N-1)/2しかない。一方、D次元の空間にN個の点なら、変数はND個ある。制限の数はほんのちょっとしかないが、一般にはほとんどの場合「解がない」のがnMDSである。変数の指数関数個制限が無い限り答えがあるというこの論文で扱っている問題に比べると随分と条件が悪い。nMDSはそれだけ難しい問題、ということか?まあ、当該論文を僕が理解してないだけかもしれない。

|

« 学会誌編集委員会 | トップページ | 粉粒体の論文(続報) »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: Nature 論文: 一般制限問題の解の存在:

« 学会誌編集委員会 | トップページ | 粉粒体の論文(続報) »