# Complexity of computing symmetries of a polynomial

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?

• "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 ​ ? ​ ​ ​ ​ ​ ​ ​ ​ – user12859 Sep 18 '16 at 12:37
• 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. ​ ​ – user12859 Sep 18 '16 at 12:39
• @RickyDemer I guess the OP means "a generating set". – Yuval Filmus Sep 18 '16 at 15:39
• How is the polynomial given to you? Also, does there always exist a small generating set? – Yuval Filmus Sep 18 '16 at 15:40
• 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. – D.W. Sep 19 '16 at 2:47