Daniel Kunkle 과 Gene Cooperman이 쓴 26f 회전 에 관한 논문입니다.
논문이 잘못된 것을 Herbert Kociemba가 지적하고 이것을 수용한 내용 일부를 발췌합니다.
전체 내용은 다음 사이트를 참조하시면 됩니다.


Some comments on the paper

I invested some time to study the paper in more detail. It's a nice result to know that it takes max 16 moves to go from any cube position to the square group H. The methods used seem similar to those, Silviu Radu, Tom Rokicki, Bruce Norskog... and I use to do computations for related problems. The perfect hash functions applied to symmetrized group elements or symmetrized cosets are called sym-coodinates in my diction for example.

There is a serious gap in the proof, that 26 moves suffice though. I already told this Daniel Kunkle and he agreed with this. In the paper they want to show that all cubes which have a distance <=3 from the square group H can be solved in maximal 14 moves. For this they compute for all 23 cosets at level 3 the 624 cases which take 12 or 13 when they have reached H with the aid of cube explorer and show that the optimal solution is <=14 moves.

The problem is that *both* the 23 cosets and the 624 H-elements are symmetry reduced. But if you take the symmetry reduced coset-elements, you must combine them with *all* H-elements at depth 12 and 13. So you have to analyse 48 times more cubes in the worst case. If any of these cubes have a 15 move optimal solution, the upper bound does not hold any more with this argumentation.


Symmetry Problem Fixed for Proof of 26

As Herbert mentioned, there was an error in our original ISSAC '07 publication announcing our proof that 26f suffice for the cube. Specifically, we reduced both levels 12 and 13 of the square subgroup and the level 3 cosets by symmetry, when in fact only one can be reduced for a correct result.

We have since gone back and re-done the computation, this time using the full subgroup (without symmetry reduction). Unfortunately, a few configurations were found that required 15 moves, hence allowing only a reduction of 1 move at coset level 3. Through further analysis, we have performed the same computation at further levels. We finally removed all cases at coset level 9. This required significant additional computation, and the use of the "brute-forcing" method we mention at the end of the paper.

This fix was presented this week at ISSAC '07, and will appear in a later journal version of the paper. We will likely also provide a fixed version of the paper online in the mean time.

Thanks very much to Herbert for his careful reading of our paper, and for bringing this mistake to our attention (among his other very useful comments). Also, thanks to all of the other researchers in this area (some of which Herbert mentioned). Our result would not have been possible without the methods and results that came before.