計算困難問題

計算が難しいといわれる問題の代表として「巡回セールスマン問題」があります。これは、「ＮＰ困難」の問題といわれます。巡回セールスマン問題、Traveling　Salesman Problem　とは、都市の集合と各都市間の移動コスト（例えば距離）が与えられたとき、全ての都市を丁度1度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める、組み合わせ最適化問題です。　
　都市の数を30とします。ある都市を出発して、その都市に戻る組み合わせは、ほぼ30の階乗、すなわち、2.65X10の32乗、すなわち約10の30乗といわれます。これを日本で最高のスーパーコンピューター「京」で計算しても1000万年かかるそうです。これは事実上、計算不可能ということです。
ところが、現在、アメリカで開発中の「量子コンピューター」が、十分なレベルに到達すると、これを使って「巡回セールスマン問題」を短時間に計算できる可能性があるそうです。「量子コンピューター」は従来のコンピューター（ノイマン・コンピュター）と原理が根本的に異なり、量子の不思議な性質（1とゼロを重ね合わせた状態が存在すること）を使うそうです。ところで、根本原理の発想と超電導を利用した量子回路制御分野では日本の技術が貢献しているそうです。

さて、一方では、将棋の必勝法を計算できるかという問題があります。将棋は駒を並べた時、
先手が指すことができる手の種類は30手です。将棋は平均して110手程度で勝負がつきます。
勝負がつくまでの手数の組み合わせは30の110乗、すなわち、3.04X10の162乗にもなります。
将棋の必勝法は「セールスマン巡回問題」のようなNP困難問題とは異なりますが、計算するべき組み合わせは、「セールスマン巡回問題」よりもはるかに大きく、計算は不可能に近い気がします。
　ただし、特定の局面を与えて、「次の最善の一手」をパソコンを使って、モンテカルロ法などで発見することに限れば、勝負をつけるという結果においてその実力はプロ棋士に匹敵するまでになりました。（これは、将棋の必勝法を計算する事とは、意味が異なります。ある局面を対象にして、勝負に勝つ可能性の高い一手を見つける事と、必勝法を計算する事は、問題の質が異なるし、計算量にも大差があると思われます。）