标题： 魔方的半神数 显示英文标题

标题： A Demigod's Number for the Rubik's Cube

摘要： 现在众所周知，任意状态的$3\times 3 \times 3$魔方都可以在最多 20 步内解决，这个结果通常被称为“上帝数”。 然而，Rokicki 等人证明这一结果花费了大约 35 个 CPU 年，因此很难重现。 我们提供了一种新颖的方法，以高置信度得到一个更差的上界 36 步，但这种方法有两个主要优势：(i) 它易于理解、重现和验证；(ii) 我们的主要思想可以推广到其他顶点传递图的直径上界估计，误差不超过其真实值的两倍，因此我们将其称为“半神数”。 我们的方法基于这样一个事实：对于顶点传递图，顶点之间的平均距离最多是直径的一半，并且通过均匀采样随机状态并使用现代求解器来获得它们距离的上界，标准的集中性界允许我们有信心地断言平均距离约为$18.32 \pm 0.1$，由此得出直径最多为$36$。 显示英文摘要

摘要： It is well-known by now that any state of the $3\times 3 \times 3$ Rubik's Cube can be solved in at most 20 moves, a result often referred to as "God's Number". However, this result took Rokicki et al. around 35 CPU years to prove and is therefore very challenging to reproduce. We provide a novel approach to obtain a worse bound of 36 moves with high confidence, but that offers two main advantages: (i) it is easy to understand, reproduce, and verify, and (ii) our main idea generalizes to bounding the diameter of other vertex-transitive graphs by at most twice its true value, hence the name "demigod number". Our approach is based on the fact that, for vertex-transitive graphs, the average distance between vertices is at most half the diameter, and by sampling uniformly random states and using a modern solver to obtain upper bounds on their distance, a standard concentration bound allows us to confidently state that the average distance is around $18.32 \pm 0.1$, from where the diameter is at most $36$.