Message #3005

From: Manfred Warmuth <manfred@soe.ucsc.edu>
Subject: Two basic open problems re the n^3 Rubik’s cube
Date: Sun, 25 May 2014 10:30:55 -0700

*Warning - These problems might be hard.*
*But Melinda tells me you have a high pain threshold*

Consider the n^3 dimensional Rubik’s cube.

Is the following problem NP complete?

*1.*
Input: A start configuration of the n^3 cube and a number of moves l.
Question: Is there a solution of length <= l?

Details: You need to fix the allowable set of single twists
to fully specify the problem: 90, 180, slice moves?

The corresponding problem of the n^2-1 shifting tile
problem is known to be NP hard:
http://users.soe.ucsc.edu/~manfred/pubs/J15.pdf

Partial results of the above Rubik cube question are given in
http://arxiv.org/abs/1106.5736
(This paper was pointed out to me by Richard Korf)

*2.*
Is there an efficient approximation algorithm,
ie is there a polynomial time algorithm for the following:

Input: A start configuration s of the n^3 cube.
Output: A solution of length <= c * opt(s), where
opt(s) is the shortest solution for solving s
and c is a fixed constant > 1.

For the shifting tile problem a polynomial time approximation algorithm
with a fixed constant factor is known, even thought the
constant factor has not been optimized.
http://users.soe.ucsc.edu/~manfred/pubs/J15.pdf

_____________________________

Prof. Manfred Warmuth
Dep. of Computer Science
Univ. of Calif. at Santa Cruz
E2 Building, MS: SOE 3
Santa Cruz, CA 95064

manfred@cse.ucsc.edu
http://www.cse.ucsc.edu/~manfred/