ブライアン・ヘイズ著「ベッドルームで群論を」（みすず書房）を読んだ。著者は、科学ジャーナリストということであるが、彼の旺盛な探究心と著作内容のレベルの高さに驚いた。一流の科学ジャーナリストというものは、単に耳学問的に得た科学知識を披露するだけでなく、学者や研究者の成果を紹介するとともに、自分自身の探究の成果を加えて読者にレベルの高い読み物を提供しているのだろうか。
ヘイズの１０編以上あるエッセイの中で、特に興味を引かれるのが、「一番簡単な難問」と題するエッセイである。ここでは、数学の組合せ論に現れる数の分割という問題が扱われているが、数学的な探究にとどまらず、物理学の相転移や統計力学との関連について言及されている。例えば、数の分割問題を隣り合うスピンが互いに逆方向を向いている反強磁性体の物理との関連で説明している。ある温度の下で、強磁性体や反強磁性体がどのようなエネルギーとエントロピーのときに安定になるのかを定量的に扱うのは容易でないようにみえる。
さて、本題に戻って、数の分割問題など組合せ論的な問題に現れる相転移の話題に絞って話を進めよう。この著作で扱われている数の分割問題とは、例えば、
｛2,10,3,8,5,7,9,5,3,2｝
のように１から１０までの範囲からでたらめに選ばれた１０個の数を２つの組に分割するときに各組に属する数の和が等しくなるような分割を見つけることである。例えば
｛2,5,3,10,7｝と｛2,5,3,9,8｝
のように分割したとき、どちらの組も和は２７となり、完璧な分割が得られる。この例の場合、両組の数の和が等しくなるように分割する方法は２３通りある。
数の分割問題を扱う簡単な方法として、欲張りアルゴリズムと呼ばれる方法が知られている。この方法は、一番大きい数から順番に、その時点で和が小さいほうの組に割り当てていくというものである。しかし、この方法を用いれば常に成功するというわけではない。例えば、
｛771,121,281,854,885,734,468,1003,83,62｝
の１０個の数は完璧に分割できるが、その分割方法は一通りしかない。しかし、この問題を欲張りアルゴリズムで扱うと、完璧な分割が得られず、どうしても両組の差を３２より小さくできない。
一般的に言えば、実は、数の分割問題は、ＮＰ完全と呼ばれる超難解な問題に属するのである。クラスＰに属する問題は比較的簡単に解けるが、クラスＮＰに属する問題は並外れて難しい問題として知られ、その中でもＮＰ完全と呼ばれる問題は、特に難しい問題とされている。
数の分割問題は、問題が大きくなればなるほど難しくなる。問題の大きさは、分割すべき整数の個数ｎと代表的な整数の桁数ｍをかけたもので表わされる。ここで、ｍは２進数、すなわちビット数で表わすことになっている。実は、数の分割問題の難しさをよく表しているのは、ｍとｎの積ではなく、ｍ／ｎという比である。ｍ＜ｎであれば、ほとんどの場合、完璧な分割がたくさん存在することになる。しかも、ｍに比べてｎが大きくなるほど解の数が増えていく。一方、ｍ＞ｎの領域では、最良の解はほぼつねに１つしかなく、そのうえめったに完璧でなくなる。
そうすると、ｍ＝ｎ附近に難しい問題と簡単な問題のあいだの境界があることになる。分割問題がこの境界を越えたとたんに、ちょうど水が沸騰したり凍ったりするように、相転移を起こすのである。つまり、ｍ＞ｎの領域では氷の状態、ｍ＜ｎの領域では水あるいは水蒸気の状態に相当するのである。ｍ＞ｎの領域では、数の組合せの状態が高々１つしかないのであるから、エントロピーが０の状態に相当する。ｍ＜ｎの領域では、数の組合せの状態が多数存在するのだから、エントロピーが高い状態に相当するわけである。
次に、他の組合せ最適化問題についても同様の相転移が現れるか否か、調べてみよう。例として、集合被覆問題というものをとりあげよう。例えば、台集合
Ｓ＝｛1,2,3,4,5,6,7,8,9,10,11,12,13,14｝
の部分集合
Ｓ１＝｛1,8｝，Ｓ２＝｛2,3,9,10｝，Ｓ３＝｛4,5,6,7,11,12,13,14｝，
Ｓ４＝｛1,2,3,4,5,6,7｝，Ｓ５＝｛8,9,10,11,12,13,14｝
の５つの集まり（集合族）が与えられたとき、台集合は、
Ｓ＝Ｓ１∪Ｓ２∪Ｓ３ともＳ＝Ｓ４∪Ｓ５
とも表せる。集合被覆問題とは、集合族に含まれる最小数の部分集合で、その合併が元の台集合となるもの（最小被覆）を求める問題である。
この問題に対して、欲張りアルゴリズムを適用できるが、必ずしも成功するわけではない。このアルゴリズムは、集合族の中でできるだけサイズの大きな部分集合を優先的に選択していく方法である。上記の例では、まずサイズが８のＳ３を選択し、次にＳの残りの要素に関して最大の部分集合を被覆に使うので、Ｓ２を選択する。このプロセスを繰り返していくと、Ｓ１，Ｓ２およびＳ３の合併集合が求まるが、これは最小解ではない。正解は、Ｓ４とＳ５の合併集合である。
一般的に記述すると、ｎ個の要素から成る台集合Ｓ＝｛ｅ１，ｅ２，．．．，ｅｎ｝に対してｍ個の部分集合から成る集合族＝｛Ｓ１，Ｓ２，．．．，Ｓｍ｝（Ｓｉ⊆Ｓ）が与えられている。集合族の中から適当な部分集合を選び、Ｓの最小被覆を求める問題である。集合被覆問題もＮＰ完全に属する超難解な問題なのである。
集合族のすべての部分集合（台集合Ｓを除く）を集合族とする場合には、非常に簡単な問題となる。部分集合｛ｅ１｝とＳの余集合、｛ｅ２｝とＳの余集合、・・・などがすべて正解になるからである。この場合には、解が無数に存在する。一方、ｎ，ｍを大きくし、かつ正解が一通りの部分集合の組合せしかないように集合族を構成することも可能である。
そうすると、集合被覆問題にも、どうやら易しい問題と難しい問題との分岐点があり、相転移を起こすらしいことが見えてくる。この分岐点は、ｍの大きさに依存するらしいことは推定できるが、特定することは難しい。数の分割問題に関するｍ／ｎ比が母集合に含まれる要素の個数とその桁数だけに依存するのに対し、集合被覆問題の場合には、集合族として選ぶ部分集合に任意性があり、それが問題の難しさを左右するからである。
最後に、フェルマー予想に言及しよう。フェルマー予想とは、方程式
ｘｎ＋ｙｎ＝ｚｎ
がｎ＞２に対して整数解をもたないことを証明する問題である。長らく解けなかったフェルマー予想が近年になって解決され、数学界を賑わしたことは、まだ記憶に新しい。この問題は、整数の集合の中から方程式を満たす部分集合｛ｘ，ｙ，ｚ｝を求める問題であるから、一種の組合せ論に属するのではなかろうか。あるいは、整数の組｛ｘ，ｙ，ｚ｝が与えられた方程式を充足するか否か判定する問題とも言えるので、充足可能性問題に属するのだろうか。
ｎ＝１，２ならば、この方程式には無数の整数解がある。しかし、ｎ＞２となると、とたんに解がなくなるので、ｎ＝３を境界として相転移を起こしていると言えるのであろう。