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

From: Manfred Warmuth <manfred@soe.ucsc.edu>
Date: Sun, 1 Jun 2014 17:14:57 -0500
Subject: 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

Hi Manfred,

I found the following post =
online:

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



Near the bottom, he writes:

ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-wid=
th:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-l=
eft:1ex">
The 15-puzzle, Rubik's cube, and dozens of other puzzles are all instan=
ces of the following family of puzzles. Fix a set of permutations, called g=
enerators, of some finite set; given a single permutation =CF=80, your task=
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 cubelet faces, and the generators describe the effect of turning a s=
ingle 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 sim=
plified and reanalyzed by Knuth. Jerrum proved that the corresponding optim=
ization 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 complexity, so membership in NP is too much to hope for.<=
/blockquote>

I removed formatting here, but the post contains links =
to the relevant papers. =C2=A0It sounds like your first question may be a s=
pecial case of the second decision problem mentioned (Can =CF=80 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. =C2=A0Compu=
tational complexity is outside my comfort zone, but your questions were sti=
ll interesting enough to go poke around the web a little bit.
>
Cheers,
Roice

gmail_extra">

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

x #ccc solid;padding-left:1ex">






=20=20=20=20=20=20=20=20

















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

all">
Consider the n^3 dimensional Rubik's cube.
>

Is the following problem NP complete?

<=
b>1.
Input: A start configuration of the n^3 cube and a numbe=
r of moves l.
Question: Is there a solution of length <=3D l?<=
/div>


Details: You need to fix the allowable set of single tw=
ists
to fully specify the problem: 90, 180, slice moves?
v>
The corresponding problem of the n^2-1 shifting tile


problem is known to be NP hard:

Partial results of the =
above Rubik cube question are given in=C2=A0


(This paper was pointed out to me by Ri=
chard Korf)

2.
Is there an effici=
ent approximation algorithm,


ie is there a polynomial time algorithm for the following:
<=
br>
Input: A start configuration s of the n^3 cube.
Out=
put: A solution of length <=3D c * opt(s), where=C2=A0
opt(s) =
is the shortest solution for solving s=C2=A0


and c is a fixed constant > 1.

For the shi=
fting tile problem a polynomial time approximation algorithm
with=
a fixed constant factor is known, even thought the
constant fact=
or has not been optimized.


>

_____________________________

Prof. Manfred Warmuthr>
Dep. of Computer Science

Univ. of Calif. at Santa Cruz
E2 Building, MS: SOE 3
Santa Cruz, CA 9=
5064


manfred@cse.u=
csc.edu

nk">http://www.cse.ucsc.edu/~manfred/
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=































--001a1133c2bae8ae8c04facd9b00--




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



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



On 6/1/2014 3:14 PM, Roice Nelson
">roice3@gmail.com [4D_Cubing] wrote:


cite=3D"mid:CAEMuGXq2XN4zCj70Br0H1v=3DLa7afBf+OdnXGx92vJO=3DH1+qA1A@mail.gm=
ail.com"
type=3D"cite">


Hi Manfred,



I found the following post online:




href=3D"http://3dpancakes.typepad.com/ernie/2010/06/complexity-of-rubiks-cu=
be.html">http://3dpancakes.typepad.com/ernie/2010/06/complexity-of-rubiks-c=
ube.html






Near the bottom, he writes:




0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-=
style:solid;padding-left:1ex">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 pr=
oduct
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 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 generators?) in polynomia=
l
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 complexity, so membership in NP
is too much to hope for.




I removed formatting here, but the post contains links to
the relevant papers. =C2=A0It 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 length at most k?), so
perhaps that gives the answer to (1).




Hope this is helpful and not too off track. =C2=A0Computationa=
l
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 href=3D"mailto:manfred@soe.ucsc.edu">manfred@soe.ucsc.edu
[4D_Cubing] < href=3D"mailto:4D_Cubing@yahoogroups.com" target=3D"_blank">4=
D_Cubing@yahoogroups.com
>

wrote:

.8ex;border-left:1px #ccc solid;padding-left:1ex">





Warning - These problems might be hard.b>
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:





Partial results of the above Rubik cube
question are given in=C2=A0


(This paper was pointed out to me by Richard
Korf)




2.

Is there an efficient approximation algorithm,v>
ie is there a polynomial time algorithm for the
following:










_____________________________



Prof. Manfred Warmuth

Dep. of Computer Science

Univ. of Calif. at Santa Cruz

E2 Building, MS: SOE 3

Santa Cruz, CA 95064



href=3D"mailto:manfred@cse.ucsc.edu" target=3D"_blank">=
manfred@cse.ucsc.edu


href=3D"http://www.cse.ucsc.edu/%7Emanfred/"
target=3D"_blank">http://www.cse.ucsc.edu/~manfred/
=


=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0













=20=20=20=20=20=20







--------------080809020401060206020705--





Return to MagicCube4D main page
Return to the Superliminal home page