Given a polynomial $f\in\mathbb{F}[x_1,\ldots,x_n]$ what is the computational complexity of computing a generating set of the automorphism group of $f$? On first look this seems like a hard problem (at the least NP-hard). Is the complexity of the above problem studied earlier?

  • 1
    $\begingroup$ "the automorphism group of $\hspace{.04 in}$f" in the sense of ​ ​ ​ permutation matrices or signed permutation matrices or generalized permutation matrix or vector space automorphism or affine automorphisms ​ ? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Sep 18 '16 at 12:37
  • $\begingroup$ In any case, it seems like the group can easily have lots of [generating sets with the minimum number of elements], and even [closed-under-inverse generating sets with the minimum number of elements for such generating sets], so "the generating set" probably needs clarification. ​ ​ $\endgroup$ – user12859 Sep 18 '16 at 12:39
  • $\begingroup$ @RickyDemer I guess the OP means "a generating set". $\endgroup$ – Yuval Filmus Sep 18 '16 at 15:39
  • 1
    $\begingroup$ How is the polynomial given to you? Also, does there always exist a small generating set? $\endgroup$ – Yuval Filmus Sep 18 '16 at 15:40
  • $\begingroup$ Also, what field $\mathbb{F}$ are you working in? Are you working in a finite field? In $\mathbb{Q}$? Something else? This might affect the result, so include as much information as you can in your question. $\endgroup$ – D.W. Sep 19 '16 at 2:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.