Max Home IndustryЕсли вам сложно собрать кубик Рубика, вам будет приятно узнать, что это действительно так. Теперь доказано, что определение разрешимости случайного куба ровно за n ходов является NP полным.
Кубик Рубика — комбинаторная головоломка, породившая много интересной математики. Например, мы знаем, что любой куб 3x3x3 можно собрать не более чем за 20 ходов, и это известно как «число бога», потому что предполагается, что для того, чтобы знать его, вы должны быть богом. Я полагаю, что 20 ходов — это не так много для любой начальной точки для куба 3x3x3, и это говорит о том, что задача в конце концов не так уж и сложна. Это кажется тем более примечательным, когда вам говорят, что существует 43 252 003 274 489 856 000 потенциальных позиций. Для решения большинства решений требуется от 15 до 19 ходов. Есть только около 300000000 позиций, требующих 20 ходов для достижения решения.
Однако стоит отметить, что мы не знаем числа бога для любого большего куба. Потребовалось несколько лет вычислительного времени, чтобы найти значение для куба 3x3x3 с помощью вычисления грубой силы. Аналогичным образом найти значение для кубиков большего размера потребовалось бы слишком много времени.
Что мы действительно знаем, так это то, что число бога увеличивается как n2 / log n. Это результат, который был получен Эриком Демейном, Сарой Эйзенстат и Михаилом Рудой — командой, которая показала последний результат.
Сначала мы должны превратить кубик Рубика в задачу решения. Можно ли собрать конкретный куб ровно за n ходов? Это проблема NP, потому что, если вы дадите мне последовательность из n ходов, которая решает куб, я могу проверить и, следовательно, доказать, что ее можно решить за n ходов за полиномиальное время. Однако, если у меня нет решения, переданного мне для проверки, оказывается, что это сложная проблема. На самом деле это полная проблема NP, что означает, что если вы можете найти для нее полиномиальное решение, то вы нашли решение для всех проблем в NP и доказали, что NP = P, что принесет вам приз в миллион долларов от Институт математики Клэя — не говоря уже о славе и богатстве, а также о ключах ко всем системам шифрования, которые мы используем в настоящее время.
Ключ к доказательству этого — показать, что проблема такая же, как поиск маршрута, который посещает узлы определенного графа только один раз, гамильтонов цикл — и эта проблема, как известно, является NP-полной.
Таким образом, ответ на вопрос о том, можно ли собрать конкретный куб за n ходов, является NP полным и, следовательно, NP трудным. Если P = NP, становится все более вероятным, что мы никогда не узнаем число Бога ни для чего, кроме куба 3x3x3.