<p>For general finite groups computations of diameters is NP-hard:
&quot;NP-hard even for elementary abelian 2-groups (<a href="https://doi.org/10.1016/0196-6774(81)90029-8" rel="nofollow noreferrer">Even, Goldreich 1981</a>)&quot;
(quote from page 4 of <a href="https://www.math.auckland.ac.nz/%7Econder/SODO-2012/Seress-SODO2012.pdf" rel="nofollow noreferrer">Ákos Seress slides</a>).</p>
<p><strong>Question:</strong> For NxNxN Rubik's groups - the computation of the diameters is also NP-hard ?</p>
<p><strong>What is known:</strong> Estimation is <span class="math-container">$C*Nˆ2/log(N)$</span> (<a href="https://arxiv.org/abs/1106.5736" rel="nofollow noreferrer">Erik D. Demaine, et.al. 2011</a> ) with optimal <span class="math-container">$C$</span> seems to be  unknown (see also <a href="https://quomodocumque.wordpress.com/2011/07/17/should-you-be-surprised-by-the-diameter-of-the-nxnxn-rubiks-group/" rel="nofollow noreferrer">JSE blog</a>), for 3x3x3 it is 20/26 (Tomas Rokicki et.al. <a href="https://cube20.org/" rel="nofollow noreferrer">https://cube20.org/</a>) , recent precise conjectures for 4x4x4 ( 48 (41)) and  5x5x5 (68 (58))  ( <a href="https://arxiv.org/abs/2404.07337" rel="nofollow noreferrer">So Hirata, 2024</a> ).</p>
<p>Recent challenge on Kaggle platform produced solutions <a href="https://www.kaggle.com/competitions/santa-2023/discussion/539970" rel="nofollow noreferrer">around <span class="math-container">$3 Nˆ2$</span></a> , so might be  diameters are less than <span class="math-container">$3 Nˆ2/log(N)$</span> <a href="https://i.sstatic.net/41e21wLj.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/41e21wLj.png" alt="enter image description here" /></a>
Figure with lengths of solutions from the Kaggle Challenge.</p>
<p>PS</p>
<p>Related question on Mathoverflow: <a href="https://mathoverflow.net/q/481936/10446">https://mathoverflow.net/q/481936/10446</a></p>

CC BY-SA 4.0
2024-11-11T09:45:14.093Z
What exactly is the input here? If $N$ is given in unary (which is the natural thing to do, and is consistent with the setup in Even and Goldreich), and if the generators of the Rubik cube group are fixed to be the standard ones, then the output of the function is just a single number for each input length. Thus, the function is trivially in $\mathrm{FP/poly}$, and cannot be $\mathrm{NP}$-hard unless $\mathrm{NP\subseteq P/poly}$ and the polynomial hierarchy collapses to $\mathrm{PH=\Sigma^P_2=\Pi^P_2=O^P_2}$.
Emil Jeřábek
CC BY-SA 4.0
2024-11-11T10:09:24.147Z
@EmilJeřábek Thanks for the comment. "N" is size of the cube's face. Thus cube have 6*Nˆ2 tiles. And the group is subgroup of $S_{6Nˆ2}$ which size is factorial in $N$. So running the brute-force algorithm like BFS would require more than N factorial operations. Thus, would you be so kind to comment why "the function is trivially in FP/poly" ?
Alexander Chervov
CC BY-SA 4.0
2024-11-11T10:12:21.013Z
Please look up the definition of P/poly if you do not know it. The complexity of the brute force algorithm is irrelevant. The result for a given input length is a single short number, which can be taken as the advice string for the given input length, thus the FP/poly function simply copies the advice to the output.
Emil Jeřábek
CC BY-SA 4.0
2024-11-11T10:21:02.247Z
@EmilJeřábek  "The complexity class FP is the set of function problems that can be solved by a deterministic Turing machine in polynomial time" . I am not sure how the "polynomial time" in $N$ can be achieved ?
Alexander Chervov
CC BY-SA 4.0
2024-11-11T10:24:09.787Z
Not FP. FP/**poly**, for the third time. Here, I googled P/poly for you: https://en.wikipedia.org/wiki/P/poly , https://complexityzoo.net/Complexity_Zoo:P#ppoly . FP/poly is the corresponding function class.
Emil Jeřábek
CC BY-SA 4.0
2024-11-11T10:37:19.243Z
@EmilJeřábek well, thanks for the comments.  Would be nice of you if you can explain the intuition behind , in my mind we clearly have some problem - brute-force is not polynomial in N, while we cannot exclude that there is some clever way to get the answer without the brute-force. So stating the question in the other words - is there any theoretical reason which would prevent finding the "clever way". The result of by Even, Goldreich are of that type, claiming NP-hardness.
Alexander Chervov
CC BY-SA 4.0
2024-11-11T10:51:59.140Z
It does not seem that you actually read what I already wrote. The output of the function only depends on the input length: this is a trivial observation that does not require any sophisticated intuition. This does not make the function efficiently computable, but it precludes it from being NP-hard. See the Karp–Lipton theorem, which is mentioned in both sources I gave you. This site is for research-level questions, while this stuff is included in common textbooks such as Arora–Barak.
Emil Jeřábek
CC BY-SA 4.0
2024-11-11T11:50:12.110Z
@EmilJeřábek I would suggest you to be more calm .  You are not obliged to give any comments.   If you find something not interesting for you - just do not post comments.  I probably understand your point that  dependence only on input's lengths precludes from being NP-hard. I am interesting in practical aspects of the questions - diameters is active field of research, and only very few non-trivial examples where we know them. So more general question is understanding the reasons behind.
Alexander Chervov
CC BY-SA 4.0
2024-11-11T11:50:47.550Z
For example if we have the series of groups depending on two integer parameters A, B -  like a "Masterball" puzzle. Does your argument still applies ?
Alexander Chervov
CC BY-SA 4.0
2024-11-11T13:23:30.600Z
It seems Masterball is some Pokémon thing, but I haven’t found a description of how it operates. But anyway, it depends on what kind of parameters $A$ and $B$ are and how they relate to the intended input size parameter $n$ relative to which you want to measure the complexity, which determines whether it’s natural to present them in unary or in binary. (I.e., you want $n$ so that a brute-force solution runs in time exponential in $n$, and NP-hardness is intended to show that there is likely no solution in time polynomial in $n$, or even subexponential in $n$. E.g., for a diameter problem...
Emil Jeřábek
CC BY-SA 4.0
2024-11-11T13:29:33.343Z
... for a permutation group, a suitable choice is to take $n$ such that the group lives in $S_n$. For a Rubik cube, a more natural choice is the dimension of the cube, but this is still polynomially related to the former.) So, if $A$ and $B$ some kind of dimension-like parameters comparable to $n$, the number of possibilities for $(A,B)$ will be polynomial in $n$, whence the argument above applies (the function is in FP/poly, and can’t be NP-hard unless PH collapses etc.). OTOH, if $A$ or $B$ is more like exponential in $n$, and you use, say, the individual bits of these numbers ...
Emil Jeřábek
CC BY-SA 4.0
2024-11-11T13:33:43.767Z
... to define the group or its generators, and the parameters can be chosen relatively freely so that the number of genuinely different inputs is indeed exponential in $n$, then there is a chance of the diameter problem being NP-hard (but, of course, this would have to be proven; it does not follow just from such simple prerequisites).
Emil Jeřábek
CC BY-SA 4.0
2024-11-11T13:45:02.770Z
@EmilJeřábek Thank you ! That is quite valuable explanations. 
Concerning Masterball or Globe - that seems to be not expontial in "n". 
You need to decompose n = A*B and then generators are some swaps and cycle shifts: see pictures e.g. https://math.stackexchange.com/q/4848434/21498
https://mathoverflow.net/q/462618/10446
Alexander Chervov
CC BY-SA 4.0
2024-11-11T13:49:39.113Z
Is there any complexity theory ideas/classes that would somehow reflect the situation where the naive brute-force computation is exponential in "n" , and we are asking about possibility/or forbid that possibility to invent "clever ways" of getting the answers ? Not sure that is is phrased clearly - but keep example of diameter in mind - naive way is factorial in n complexity, while sometimes there is clever way to determine the answer.
Alexander Chervov
CC BY-SA 4.0
2024-11-11T19:05:03.780Z
You can simply ask directly whether the problem is computable in time subexponential in $n$ (with the understanding that the answer, if any, will likely be conditional on some complexity-theoretic assumptions).
Emil Jeřábek
CC BY-SA 4.0
2024-11-18T03:20:56.867Z
You could also ask the complexity when the input n is given in binary, so the input size is log(n) bits, and the brute force algo is something like doubly exponential in the input size. And then ask whether it is complete for the corresponding class or not. (For unary input, you don't need FP/poly and Karp-Lipton - Mahaney gives you that no sparse decision problem is NP-hard assuming only P neq NP. And you can turn this into one by adding another parameter k and asking if the diameter is at least k.)
Joshua Grochow
<graph-theory><np-hardness><gr.group-theory>
Determining diameters of NxNxN Rubik's cubes - is NP-hard problem?
Alexander Chervov
# Determining diameters of NxNxN Rubik's cubes - is NP-hard problem?

(Asked by: username_0 on 2024-11-10)

For general finite groups computations of diameters is NP-hard:
"NP-hard even for elementary abelian 2-groups ([Even, Goldreich 1981](https://doi.org/10.1016/0196-6774(81)90029-8))"
(quote from page 4 of [Ákos Seress slides](https://www.math.auckland.ac.nz/%7Econder/SODO-2012/Seress-SODO2012.pdf)).

**Question:** For NxNxN Rubik's groups - the computation of the diameters is also NP-hard ?

**What is known:** Estimation is $C\*Nˆ2/log(N)$ ([Erik D. Demaine, et.al. 2011](https://arxiv.org/abs/1106.5736) ) with optimal $C$ seems to be unknown (see also [JSE blog](https://quomodocumque.wordpress.com/2011/07/17/should-you-be-surprised-by-the-diameter-of-the-nxnxn-rubiks-group/)), for 3x3x3 it is 20/26 (Tomas Rokicki et.al. <https://cube20.org/>) , recent precise conjectures for 4x4x4 ( 48 (41)) and 5x5x5 (68 (58)) ( [So Hirata, 2024](https://arxiv.org/abs/2404.07337) ).

Recent challenge on Kaggle platform produced solutions [around $3 Nˆ2$](https://www.kaggle.com/competitions/santa-2023/discussion/539970) , so might be diameters are less than $3 Nˆ2/log(N)$ [![enter image description here](https://i.sstatic.net/41e21wLj.png)](https://i.sstatic.net/41e21wLj.png)
Figure with lengths of solutions from the Kaggle Challenge.

PS

Related question on Mathoverflow: <https://mathoverflow.net/q/481936/10446>

**Tags:** graph-theory, np-hardness, gr.group-theory
> **Comments:**
> **username_1**: What exactly is the input here? If $N$ is given in unary (which is the natural thing to do, and is consistent with the setup in Even and Goldreich), and if the generators of the Rubik cube group are fixed to be the standard ones, then the output of the function is just a single number for each input length. Thus, the function is trivially in $\mathrm{FP/poly}$, and cannot be $\mathrm{NP}$-hard unless $\mathrm{NP\subseteq P/poly}$ and the polynomial hierarchy collapses to $\mathrm{PH=\Sigma^P_2=\Pi^P_2=O^P_2}$.  
> **username_0**: @EmilJeřábek Thanks for the comment. "N" is size of the cube's face. Thus cube have 6*Nˆ2 tiles. And the group is subgroup of $S_{6Nˆ2}$ which size is factorial in $N$. So running the brute-force algorithm like BFS would require more than N factorial operations. Thus, would you be so kind to comment why "the function is trivially in FP/poly" ?  
> **username_1**: Please look up the definition of P/poly if you do not know it. The complexity of the brute force algorithm is irrelevant. The result for a given input length is a single short number, which can be taken as the advice string for the given input length, thus the FP/poly function simply copies the advice to the output.  
> **username_0**: @EmilJeřábek  "The complexity class FP is the set of function problems that can be solved by a deterministic Turing machine in polynomial time" . I am not sure how the "polynomial time" in $N$ can be achieved ?  
> **username_1**: Not FP. FP/**poly**, for the third time. Here, I googled P/poly for you: https://en.wikipedia.org/wiki/P/poly , https://complexityzoo.net/Complexity_Zoo:P#ppoly . FP/poly is the corresponding function class.  
> **username_0**: @EmilJeřábek well, thanks for the comments.  Would be nice of you if you can explain the intuition behind , in my mind we clearly have some problem - brute-force is not polynomial in N, while we cannot exclude that there is some clever way to get the answer without the brute-force. So stating the question in the other words - is there any theoretical reason which would prevent finding the "clever way". The result of by Even, Goldreich are of that type, claiming NP-hardness.  
> **username_1**: It does not seem that you actually read what I already wrote. The output of the function only depends on the input length: this is a trivial observation that does not require any sophisticated intuition. This does not make the function efficiently computable, but it precludes it from being NP-hard. See the Karp–Lipton theorem, which is mentioned in both sources I gave you. This site is for research-level questions, while this stuff is included in common textbooks such as Arora–Barak.  
> **username_0**: @EmilJeřábek I would suggest you to be more calm .  You are not obliged to give any comments.   If you find something not interesting for you - just do not post comments.  I probably understand your point that  dependence only on input's lengths precludes from being NP-hard. I am interesting in practical aspects of the questions - diameters is active field of research, and only very few non-trivial examples where we know them. So more general question is understanding the reasons behind.  
> **username_0**: For example if we have the series of groups depending on two integer parameters A, B -  like a "Masterball" puzzle. Does your argument still applies ?  
> **username_1**: It seems Masterball is some Pokémon thing, but I haven’t found a description of how it operates. But anyway, it depends on what kind of parameters $A$ and $B$ are and how they relate to the intended input size parameter $n$ relative to which you want to measure the complexity, which determines whether it’s natural to present them in unary or in binary. (I.e., you want $n$ so that a brute-force solution runs in time exponential in $n$, and NP-hardness is intended to show that there is likely no solution in time polynomial in $n$, or even subexponential in $n$. E.g., for a diameter problem...  
> **username_1**: ... for a permutation group, a suitable choice is to take $n$ such that the group lives in $S_n$. For a Rubik cube, a more natural choice is the dimension of the cube, but this is still polynomially related to the former.) So, if $A$ and $B$ some kind of dimension-like parameters comparable to $n$, the number of possibilities for $(A,B)$ will be polynomial in $n$, whence the argument above applies (the function is in FP/poly, and can’t be NP-hard unless PH collapses etc.). OTOH, if $A$ or $B$ is more like exponential in $n$, and you use, say, the individual bits of these numbers ...  
> **username_1**: ... to define the group or its generators, and the parameters can be chosen relatively freely so that the number of genuinely different inputs is indeed exponential in $n$, then there is a chance of the diameter problem being NP-hard (but, of course, this would have to be proven; it does not follow just from such simple prerequisites).  
> **username_0**: @EmilJeřábek Thank you ! That is quite valuable explanations.  Concerning Masterball or Globe - that seems to be not expontial in "n".  You need to decompose n = A*B and then generators are some swaps and cycle shifts: see pictures e.g. https://math.stackexchange.com/q/4848434/21498 https://mathoverflow.net/q/462618/10446  
> **username_0**: Is there any complexity theory ideas/classes that would somehow reflect the situation where the naive brute-force computation is exponential in "n" , and we are asking about possibility/or forbid that possibility to invent "clever ways" of getting the answers ? Not sure that is is phrased clearly - but keep example of diameter in mind - naive way is factorial in n complexity, while sometimes there is clever way to determine the answer.  
> **username_1**: You can simply ask directly whether the problem is computable in time subexponential in $n$ (with the understanding that the answer, if any, will likely be conditional on some complexity-theoretic assumptions).  
> **username_2**: You could also ask the complexity when the input n is given in binary, so the input size is log(n) bits, and the brute force algo is something like doubly exponential in the input size. And then ask whether it is complete for the corresponding class or not. (For unary input, you don't need FP/poly and Karp-Lipton - Mahaney gives you that no sparse decision problem is NP-hard assuming only P neq NP. And you can turn this into one by adding another parameter k and asking if the diameter is at least k.)  

---

## 0 answers

