Thread: "Two basic open problems re the n^3 Rubik's cube"

--001a1133c2bae8ae8c04facd9b00
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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 =CF=80, your t=
ask is
> to express =CF=80 as a product of a sequence of generators. For example, =
for the
> n=C3=97n=C3=97n Rubik's cube, the ground set is the set of 6n=C2=B2 cubel=
et 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 =CF=80 be written as a sequence of gener=
ators?)
> in polynomial time; the algorithm was later simplified and reanalyzed by
> Knuth. Jerrum proved that the corresponding optimization problem (Can =CF=
=80 be
> written as a sequence of length at most k?) is PSPACE-complete. For some
> permutation puzzles, the shortest solution can have exponential complexit=
y,
> 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 =CF=80 be written as a sequence of l=
ength
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 <=3D 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 <=3D 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/
>
>
>
>=20
>

--001a1133c2bae8ae8c04facd9b00
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

--------------080809020401060206020705
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: quoted-printable

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

BTW, I'm especially tickled to see Donald Knuth's work intersect our=20
favorite subject. I suggest that we take the suggestion in his abstract=20
to shorten=20
"permutation" to "perm" in our discussions, seeing as how Prof. Knuth is=20
synonymous with efficiency. I also noticed that he wrote a fun paper on=20
the subject of vanity license plates. He even mentioned that the plate=20
consisting of seven blanks was still available in California as of 2009,=20
which surprised me because in 1991 I attempted to get exactly that plate=20
but was refused by a DMV clerk who simply said "no" without explanation.=20
That plate had been an idea of my father's, and now that I hear there=20
may be a chance, I may just have to try harder to get it. If not, I do=20
have another fun plate in mind, but as a programmer, the empty plate=20
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.htm=
l
>
> 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 =CF=80, your task is to express =CF=80 as a produc=
t of a
> sequence of generators. For example, for the n=C3=97n=C3=97n Rubik's =
cube,
> the ground set is the set of 6n=C2=B2 cubelet faces, and the generato=
rs
> 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 =CF=80 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 =CF=80 be written as a sequen=
ce
> 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=20
> papers. It sounds like your first question may be a special case of=20
> the second decision problem mentioned (Can =CF=80 be written as a sequenc=
e=20
> of length at most k?), so perhaps that gives the answer to (1).
>
> Hope this is helpful and not too off track. Computational complexity=20
> is outside my comfort zone, but your questions were still interesting=20
> 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=20
> [4D_Cubing] <4D_Cubing@yahoogroups.com=20
> > 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 <=3D 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 <=3D 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/
>
>
>
>
>
>
>
>=20


--------------080809020401060206020705
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable



">


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 href=3D"http://link.springer.com/article/10.1007%2FBF01375471">his
abstract 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