Message #3007

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Two basic open problems re the n^3 Rubik’s cube
Date: Sun, 01 Jun 2014 23:00:55 -0700

Wow, that’s some nice digging, Roice! Manfred, please let us know if
that helps.

BTW, I’m especially tickled to see Donald Knuth’s work intersect our
favorite subject. I suggest that we take the suggestion in his abstract
<http://link.springer.com/article/10.1007%2FBF01375471> to shorten
"permutation" to "perm" in our discussions, seeing as how Prof. Knuth is
synonymous with efficiency. I also noticed that he wrote a fun paper on
the subject of vanity license plates. He even mentioned that the plate
consisting of seven blanks was still available in California as of 2009,
which surprised me because in 1991 I attempted to get exactly that plate
but was refused by a DMV clerk who simply said "no" without explanation.
That plate had been an idea of my father’s, and now that I hear there
may be a chance, I may just have to try harder to get it. If not, I do
have another fun plate in mind, but as a programmer, the empty plate
sure would be special!

-Melinda

On 6/1/2014 3:14 PM, Roice Nelson roice3@gmail.com [4D_Cubing] wrote:
>
>
> 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
> <mailto:manfred@soe.ucsc.edu> [4D_Cubing] <4D_Cubing@yahoogroups.com
> <mailto: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
> <http://users.soe.ucsc.edu/%7Emanfred/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
> <http://users.soe.ucsc.edu/%7Emanfred/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 <mailto:manfred@cse.ucsc.edu>
> http://www.cse.ucsc.edu/~manfred/
> <http://www.cse.ucsc.edu/%7Emanfred/>
>
>
>
>
>
>
>