コンピューターでも難しい。ルービックキューブはNP完全問題だった
Image: Popartic/Shutterstock.com

コンピューターでも難しい。ルービックキューブはNP完全問題だった

いい言い訳ができました。

ルービックキューブをそろえられない方にグッドニュースです。マサチューセッツ工科大学(MIT)のコンピューターサイエンス・人工知能研究所(CSAIL)の研究チームによって、NxNxN(Nは任意の自然数)のルービックキューブがNP完全問題であることが証明されました! つまり、ルービックキューブを解くのは、コンピューターにとっても難しい問題であることを意味しています。なので、人間が解けなくても気にすることはありません。

そもそもNP完全問題って何?って話ですが、簡単に言うと、「答えが正しいかどうかのチェックはすぐにできるけれど、答え自体を見つけるのが難しい」という問題です。ルービックキューブを例に説明すると、答え(=全面をそろえる手順)が正しいかどうかは、実際に全面がそろうかやってみれば簡単に確認できますが、そもそも「全面をそろえる手順」そのものを見つけるのが難しいということになります。ルービックキューブのようなパズルだけでなく、巡回セールスマン問題など、現実世界にもNP完全問題は存在しています。

この研究成果は、論文としてarXivで公開されています。NxNxNのルービックキューブ=NP完全問題と証明するために30ページ以上も費やされていることから、ルービックキューブの難しさがひしひしと伝わってきます。ざっくりと証明方法を説明すると、まずルービックキューブを解く方法Xが存在すると仮定。Xを使ってNP完全問題であることがすでに証明されているハミルトン閉路問題を解くことができれば、XもまたNP完全問題だと証明できる、という具合です。

本当に難しい……でも細かいことは気にしなくても大丈夫。要するに、ルービックキューブは難しいし、「ルービックキューブが難しい」と証明することさえも難しいってことです。

さて、ルービックキューブはコンピューターでも難しいということが証明されたわけですが、それはあくまでNが大きいときの話です。一般的な3x3x3のルービックキューブは、人間でも解くことが可能ですよね。

現時点で、オーストラリア出身のフェリックス・ゼムデグスさんが打ち立てた4.73秒が、ルービックキューブの世界記録となっています。5秒以内で解けるなんて、頭の中にコンピューターが入ってるんじゃ!?なんて思っていたら、コンピューターは3x3x3のルービックキューブをたったの0.637秒でクリアしてしまうそうです。やっぱりコンピューターって恐ろしい......

Image: Popartic/Shutterstock.com
Source: arXiv via New Scientist, Feliks Zemdegs/YouTube

(tmyk)

あわせて読みたい

powered by