If we think of \(S_{2^k}\) (or \(A_{2^k}\) perhaps, although it doesn't really matter) as the group of alternating circuits with generating set \(A\) comprised of

• some set of universal gates acting on the first 3 bits
• all transpositions of bits

then the language \[ \left\{ (1^k, w) : w \in A^*, w =_{S_{2^k}} 1 \right\} \] is \(\mathrm{coNP}\) hard. Is there something special about this generating set or would the same be true for any \(\mathrm{poly}(k)\) sized generating set? You can't quite make the same argument you do for universal sets of gates since a priori, some generating sets may require exponentially long words to express the transposition of bits.