Message #3006

From: Roice Nelson <roice3@gmail.com>
Subject: Re: [MC4D] Two basic open problems re the n^3 Rubik’s cube
Date: Sun, 01 Jun 2014 17:14:57 -0500

Hi Manfred,

I found the following post online:

http://3dpancakes.typepad.com/ernie/2010/06/complexity-of-rubiks-cube.html

Near the bottom, he writes:

The 15-puzzle, Rubik’s cube, and dozens of other puzzles are all instances
> of the following family of puzzles. Fix a set of permutations, called
> generators, of some finite set; given a single permutation π, your task is
> to express π as a product of a sequence of generators. For example, for the
> n×n×n Rubik’s cube, the ground set is the set of 6n² cubelet faces, and the
> generators describe the effect of turning a single slice of the cube.
> Furst, Hopcroft, and Luks proved that an algorithm of Schreier and Sims
> solves the decision problem (Can π be written as a sequence of generators?)
> in polynomial time; the algorithm was later simplified and reanalyzed by
> Knuth. Jerrum proved that the corresponding optimization problem (Can π be
> written as a sequence of length at most k?) is PSPACE-complete. For some
> permutation puzzles, the shortest solution can have exponential complexity,
> so membership in NP is too much to hope for.

I removed formatting here, but the post contains links to the relevant
papers. It sounds like your first question may be a special case of the
second decision problem mentioned (Can π be written as a sequence of length
at most k?), so perhaps that gives the answer to (1).

Hope this is helpful and not too off track. Computational complexity is
outside my comfort zone, but your questions were still interesting enough
to go poke around the web a little bit.

Cheers,
Roice

On Sun, May 25, 2014 at 12:30 PM, Manfred Warmuth manfred@soe.ucsc.edu
[4D_Cubing] <4D_Cubing@yahoogroups.com> wrote:

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