Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on sets $L_n = \{ l \in L \mid |l| = n  \}$ such that there are few orbits, i.e such that $|L_n / G_n| < n^c$ for big enough $n$ and some $c$, and such that $G_n$ can be generated given $n$ efficiently?The point here is that if one finds a language/group such as this, and if one can find normal forms under polynomial time group actions in $\mathrm{FP}$, then one can reduce $L$ by a $\mathrm{PTIME}$ reduction  to a sparse language by computing the normal form for any given $N$, implying that $\mathrm{P = NP}$ or $\mathrm{L = P}$, depending on whether you chose an NP- or P-complete language initially, respectively. So it seems that either there are no such groups with sparse orbits or that computing normal forms is hard for all such groups or one of these results will hold which I think most of us don't believe. Also it would seem that if one can compute the equivalence relation over the orbits instead of the normal forms, one could still do this nonuniformly, in $\mathrm{P/poly}$. Hoping some other people have thoughts on this.
Are There Highly Symmetric NP- or P-complete Languages?
np;algebra;gr.group theory;complexity;symmetry
For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-complete language has a poly-time group action with few orbits, PH collapses. For, with this additional assumption about sampleability, the standard $\mathsf{coAM}$ protocol for Graph Isomorphism also works for testing whether two strings are in the same $G_n$-orbit. We then would have $\mathsf{NP} \subseteq \mathsf{coAM/poly} = \mathsf{coNP/poly}$, so PH collapses to $\mathsf{ZPP}^{\mathsf{NP}}$. So, to avoid collapsing PH, any such construction for NP would need the groups to not have an efficient nearly-uniform sampler.