fromageの日記： ルービックキューブはNP完全問題

Gizmodo から。

色のついていない部分がある n x n x n の一般化ルービックキューブ RCm に対して、k 回以内の回転で、6面とも色を揃えられるかどうかを判定する問題が NP 完全であることは知られていた。今回は、全部に色がついている n x n x n の一般化ルービックキューブ RC に対して、k回以内の回転で 6面とも色を揃えられるかどうかを判定する問題が NP 完全であることが示された。

ハミルトンパス問題の変形（この NP 完全性も示されている）から、このルービックキューブ問題への多項式時間還元を示すことで証明されている。

でも記事内にあるように、NP 完全問題であっても、ルービックキューブは n = 3 で固定されているので、実際に解くことができる。