Does a solution to SAT solve the HSP for $S_N$, $D_{2N}$, or even the general case?

Question

I often hear about the graph isomorphism problem reducing to the HSP with the symmetric group and a mapping $f \colon \pi \in S_N \mapsto \pi(G)$ with $G$ being some graph (the union of the graphs we’re checking). And occasionally, it is mentioned that the Shortest Vector Problem (SVP) reduces to the HSP with the dihedral group attached to it.

While it is known, very well actually, that graph isomorphism, the SVP, factoring, and so on are in NP and therefore reduce to SAT, what I don’t know is if the HSP reduces to SAT in the general case. A key point is that the HSP does not necessarily reduce back to its ‘representation’ problem. I use ‘representation’ problem here to refer to factoring, graph isomorphism and SVP.

That is, if we had a solution to SAT given as an oracle, could we solve the HSP? If not, are there exceptions?

I think that the HSP for all abelian groups (may) be in NP? But does this hold for all non-abelian groups? Am I wrong about this being true for abelian groups?

Answer 1

Your question is whether HSP for any particular sequence of finite groups lies in (functional) P^NP, i.e., the Turing reduction closure of NP. In fact, the answer is very often yes. Recall that P^NP = P^FNP; i.e., if a Turing machine can interrogate an NP oracle for existence of solutions to predicate equations p(x,y) = yes, then it can learn examples of solutions. For example, in the symmetric group S_n (here I am using little n as the subscript so that group elements have poly(n) bit complexity), a classical TM can learn from an FNP oracle whether the hidden subgroup H ⊆ S_n has a permutation f such that f(1) = k for any given k; if so, it can learn an example. Then it can ask whether there is an f ∈ H such that f(1) = 1 and f(2) = k for any given k, etc. These types of questions yield a strong generating set for H in the sense of the Shreier-Sims algorithm.

My sense is that this type of oracle algorithm is general enough that the answer is morally always yes. Possibly the only barrier is a sequence of finite groups that grows so quickly that you can't learn much about HSP in either P^FNP or in BQP or anything like it, for the basic reason that most elements don't even have polynomial-length descriptions.