<p>I've encountered a model which can be thought of as a version of the Hidden Subgroup Problem (<a href="https://en.wikipedia.org/wiki/Hidden_subgroup_problem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Hidden_subgroup_problem</a>), but that doesn't quite meet the standard problem's requirements.</p>
<p>Specifically, the universe group is <span class="math-container">$S_n$</span> (the permutation group of order <span class="math-container">$n$</span>), and is hence not Abelian. Also, my hiding function cannot be described with a low enough number of bits.</p>
<p>I'm trying to show that my problem is NP-hard (which I suspect might be the case). So,</p>
<blockquote>
<p>Are there any known NP-hard variants of the non-Abelian hidden subgroup problem?</p>
</blockquote>

CC BY-SA 4.0
2021-07-27T22:30:10.567Z
Link for the ignorant and lazy (such as myself): https://en.wikipedia.org/wiki/Hidden_subgroup_problem
Neal Young
CC BY-SA 4.0
2021-07-28T07:02:30.433Z
@NealYoung - added also to the post. Thanks.
Shaull
CC BY-SA 4.0
2021-07-28T13:36:38.090Z
Greg Kuperberg proved NP-hardness of HSP over Q, which is abelian though. To my knowledge, the paper is not published yet, but you can find the presentation in QIP'2021 at https://www.youtube.com/watch?v=HdUiO78bVdI.
Hhan
CC BY-SA 4.0
2021-07-31T21:14:43.393Z
There's a pretty canonical reduction showing that if you can efficiently solve HSP for the symmetric group $S_n$ then you can efficiently solve graph isomorphism.  I'm not sure if the reduction works the other way (e.g. if you can solve graph isomorphism efficiently then that gets you an alg. for HSP over $S_n$), but if it did then I think that would imply that HSP over $S_n$ is not likely to be **NP-hard**.  I really liked Christopher Moore's lecture on this [here](https://www.youtube.com/watch?v=m8uXQmo2A0U) - something about the traces of representations of $S_n$ play a strong role.
Mark S
CC BY-SA 4.0
2021-08-01T06:09:06.733Z
@MarkS - Thanks! I'm presuming this refers to a description of the hiding function which is similar to the Abelian HSP. Do you know anything about descriptions that e.g., require more bits for the hiding function?
Shaull
<cc.complexity-theory><np-hardness>
An NP-hard Hidden Subgroup Problem
Shaull
# An NP-hard Hidden Subgroup Problem

(Asked by: username_0 on 2021-07-27)

I've encountered a model which can be thought of as a version of the Hidden Subgroup Problem (<https://en.wikipedia.org/wiki/Hidden_subgroup_problem>), but that doesn't quite meet the standard problem's requirements.

Specifically, the universe group is $S\_n$ (the permutation group of order $n$), and is hence not Abelian. Also, my hiding function cannot be described with a low enough number of bits.

I'm trying to show that my problem is NP-hard (which I suspect might be the case). So,

> Are there any known NP-hard variants of the non-Abelian hidden subgroup problem?

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: Link for the ignorant and lazy (such as myself): https://en.wikipedia.org/wiki/Hidden_subgroup_problem  
> **username_0**: @NealYoung - added also to the post. Thanks.  
> **username_2**: Greg Kuperberg proved NP-hardness of HSP over Q, which is abelian though. To my knowledge, the paper is not published yet, but you can find the presentation in QIP'2021 at https://www.youtube.com/watch?v=HdUiO78bVdI.  
> **username_3**: There's a pretty canonical reduction showing that if you can efficiently solve HSP for the symmetric group $S_n$ then you can efficiently solve graph isomorphism.  I'm not sure if the reduction works the other way (e.g. if you can solve graph isomorphism efficiently then that gets you an alg. for HSP over $S_n$), but if it did then I think that would imply that HSP over $S_n$ is not likely to be **NP-hard**.  I really liked Christopher Moore's lecture on this [here](https://www.youtube.com/watch?v=m8uXQmo2A0U) - something about the traces of representations of $S_n$ play a strong role.  
> **username_0**: @MarkS - Thanks! I'm presuming this refers to a description of the hiding function which is similar to the Abelian HSP. Do you know anything about descriptions that e.g., require more bits for the hiding function?  

---

## 0 answers

