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?

  • 2
    $\begingroup$ Look up some work by Greg Kuperberg. He worked on some HSP problems that might be outside of NP. He guest-posted on Aaronson’s blog a couple of years back. Kuperberg expanded the continued fraction of Shor’s algorithm to the LLL algorithm to do some nontrivial HSP work on problems outside of NP if I understood. $\endgroup$ May 6, 2023 at 2:57
  • 2
    $\begingroup$ scottaaronson.blog/?p=5151 $\endgroup$ May 6, 2023 at 2:59
  • $\begingroup$ @MarkS Thank you, that is a great source. Are there similar articles for determining if the HSP with $S_N$ or $D_{2N}$ is in NP? Is it known? $\endgroup$ May 6, 2023 at 3:29
  • 1
    $\begingroup$ HSP as typically defined is certainly not in NP as typically defined for the trivial reason of a mismatch between problem types and computational models. HSP is a function problem for an oracle machine. NP is a class of decision problems for a deterministic Turing machine. See this answer for more details. $\endgroup$ May 6, 2023 at 4:03
  • $\begingroup$ @AdamZalcman Oh, yes. I was referring to “is Turing reducible to SAT” as the definition of NP in my question, not the traditional definition for languages. $\endgroup$ May 6, 2023 at 14:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.