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

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

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

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

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