<p>My intuition is that an NP-complete language of this type would cause a collapse of the polynomial hierarchy much like the one in the <a href="http://Karp%E2%80%93Lipton%20theorem" rel="noreferrer">Karp–Lipton theorem.</a></p>

<p>More specifically, if you go up to the second level of the polynomial hierarchy, you can use the power of the hierarchy to guess the equivalence between a given group element and some representative of an equivalence class, and then you're back to the Karp–Lipton case where the fact that you have polynomially many inequivalent inputs puts you in P/poly.</p>

<p>(The result should be the same as Joshua Grochow's answer, but without the added assumption of sampleability.)</p>

CC BY-SA 3.0
2017-03-17T05:23:27.523Z
It depends on the size of the group though, right? I didn't even say the group was finite, just that it acts on the language efficiently and can be generated efficiently. That being said, I'm under the impression that if the group can be sampled efficiently (as in Joshua's answer) this would allow you to solve SAT in BPP implying what you suggest. Not positive of this but there's one approach I've been chasing which uses the self reducibility of SAT and prunes this tree of reductions randomly. As far as I can tell this requires the orbits to have similar size though.
Samuel Schlesinger
CC BY-SA 3.0
2017-03-17T05:26:31.047Z
How can you act in polynomial time if it takes more than polynomial time just to write down a group element?
David Eppstein
CC BY-SA 3.0
2017-03-17T05:34:20.937Z
Plenty of infinite groups have finite presentations, no? These aren't necessarily permutation groups they just have a homomorphism to a symmetry group of our language.
Samuel Schlesinger
CC BY-SA 3.0
2017-03-17T05:35:52.433Z
That being said, I think that efficient sampleability should confine you to merely exponentially large groups anyways
Samuel Schlesinger
CC BY-SA 3.0
2017-03-17T14:01:27.983Z
I don't see it yet: the issue is that if you go up one level of the hierarchy to guess the equivalence, all you conclude is that $NP \subseteq \Pi_2 P \cap \Sigma_2 P$ (or maybe with a /poly), but that doesn't collapse the hierarchy - it's already true!
Joshua Grochow
CC BY-SA 3.0
2017-03-17T14:50:25.793Z
Oh, unless you meant the language goes one level up too, in which case I agree: no languages with few orbits can be complete for, say, $\Sigma_2 P$ without collapsing PH.
Joshua Grochow
CC BY-SA 3.0
2017-03-17T05:15:42.653Z
2017-03-17T05:15:42.653Z
David Eppstein
<p>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 <em>not</em> have an efficient nearly-uniform sampler.</p>

CC BY-SA 3.0
2017-03-16T16:29:17.620Z
Nice! This is exactly what I figured would happen after reading another answer of yours on the orbit representative problem.
Samuel Schlesinger
CC BY-SA 3.0
2017-03-16T16:27:00.440Z
2017-03-16T16:27:00.440Z
Joshua Grochow
<p>Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or <a href="https://ncatlab.org/nlab/show/groupoid" rel="noreferrer">groupoid</a>, 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| &lt; n^c$ for big enough $n$ and some $c$, and such that $G_n$ can be generated given $n$ efficiently?</p>

<p>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.</p>

CC BY-SA 3.0
2017-03-13T22:30:58.663Z
What do you mean by an "$\{NP,P\}$-complete language"?
Emil Jeřábek
CC BY-SA 3.0
2017-03-13T22:51:56.777Z
I mean a $P$ or $NP$ complete language.
Samuel Schlesinger
CC BY-SA 3.0
2017-03-14T08:08:49.450Z
Why do you think that the existence of a polytime reduction would collapse P down to L?
Emil Jeřábek
CC BY-SA 3.0
2017-03-14T08:17:08.330Z
I would've thought under log reductions but given the normal form computation would almost certainly be in P this is really only relevant for NP. Thanks for mentioning that.
Samuel Schlesinger
<np><algebra><gr.group-theory><complexity><symmetry>
Are There Highly Symmetric NP- or P-complete Languages?
Samuel Schlesinger
# Are There Highly Symmetric NP- or P-complete Languages?

(Asked by: username_0 on 2017-03-13)

Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G\_n$ (or [groupoid](https://ncatlab.org/nlab/show/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.

**Tags:** np, algebra, gr.group-theory, complexity, symmetry

> **Comments:**
> **username_1**: What do you mean by an "$\{NP,P\}$-complete language"?  
> **username_0**: I mean a $P$ or $NP$ complete language.  
> **username_1**: Why do you think that the existence of a polytime reduction would collapse P down to L?  
> **username_0**: I would've thought under log reductions but given the normal form computation would almost certainly be in P this is really only relevant for NP. Thanks for mentioning that.  

---

## 2 answers

### Answer by username_3 on 2017-03-16. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_0**: Nice! This is exactly what I figured would happen after reading another answer of yours on the orbit representative problem.  

---

### Answer by username_2 on 2017-03-17. Score: 5

My intuition is that an NP-complete language of this type would cause a collapse of the polynomial hierarchy much like the one in the [Karp–Lipton theorem.](http://Karp%E2%80%93Lipton%20theorem)

More specifically, if you go up to the second level of the polynomial hierarchy, you can use the power of the hierarchy to guess the equivalence between a given group element and some representative of an equivalence class, and then you're back to the Karp–Lipton case where the fact that you have polynomially many inequivalent inputs puts you in P/poly.

(The result should be the same as username_3's answer, but without the added assumption of sampleability.)

> **Comments:**
> **username_0**: It depends on the size of the group though, right? I didn't even say the group was finite, just that it acts on the language efficiently and can be generated efficiently. That being said, I'm under the impression that if the group can be sampled efficiently (as in Joshua's answer) this would allow you to solve SAT in BPP implying what you suggest. Not positive of this but there's one approach I've been chasing which uses the self reducibility of SAT and prunes this tree of reductions randomly. As far as I can tell this requires the orbits to have similar size though.  
> **username_2**: How can you act in polynomial time if it takes more than polynomial time just to write down a group element?  
> **username_0**: Plenty of infinite groups have finite presentations, no? These aren't necessarily permutation groups they just have a homomorphism to a symmetry group of our language.  
> **username_0**: That being said, I think that efficient sampleability should confine you to merely exponentially large groups anyways  
> **username_3**: I don't see it yet: the issue is that if you go up one level of the hierarchy to guess the equivalence, all you conclude is that $NP \subseteq \Pi_2 P \cap \Sigma_2 P$ (or maybe with a /poly), but that doesn't collapse the hierarchy - it's already true!  
> **username_3**: Oh, unless you meant the language goes one level up too, in which case I agree: no languages with few orbits can be complete for, say, $\Sigma_2 P$ without collapsing PH.  

---

