コンピューターでも難しい。ルービックキューブはNP完全問題だった2017.07.20 20:0015,593 tmyk いい言い訳ができました。 ルービックキューブをそろえられない方にグッドニュースです。マサチューセッツ工科大学(MIT)のコンピューターサイエンス・人工知能研究所(CSAIL)の研究チームによって、NxNxN(Nは任意の自然数)のルービックキューブがNP完全問題であることが証明されました! つまり、ルービックキューブを解くのは、コンピューターにとっても難しい問題であることを意味しています。なので、人間が解けなくても気にすることはありません。 そもそもNP完全問題って何?って話ですが、簡単に言うと、「答えが正しいかどうかのチェックはすぐにできるけれど、答え自体を見つけるのが難しい」という問題です。ルービックキューブを例に説明すると、答え(=全面をそろえる手順)が正しいかどうか
![コンピューターでも難しい。ルービックキューブはNP完全問題だった](https://cdn-ak-scissors.b.st-hatena.com/image/square/dcff82d85ae03e9e26f32cabfba1dc0de4d8bb8b/height=288;version=1;width=512/https%3A%2F%2Fmedia.loom-app.com%2Fgizmodo%2Fdist%2Fimages%2F2017%2F07%2F170716_lubik_cube.jpg%3Fw%3D1280%26h%3D630%26f%3Djpg)