# 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/