14
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ What do you mean by an "$\{NP,P\}$-complete language"? $\endgroup$
    – Emil Jeřábek
    Commented Mar 13, 2017 at 22:30
  • $\begingroup$ I mean a $P$ or $NP$ complete language. $\endgroup$
    – Samuel Schlesinger
    Commented Mar 13, 2017 at 22:51
  • 1
    $\begingroup$ Why do you think that the existence of a polytime reduction would collapse P down to L? $\endgroup$
    – Emil Jeřábek
    Commented Mar 14, 2017 at 8:08
  • $\begingroup$ 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. $\endgroup$
    – Samuel Schlesinger
    Commented Mar 14, 2017 at 8:17

2 Answers 2

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice! This is exactly what I figured would happen after reading another answer of yours on the orbit representative problem. $\endgroup$
    – Samuel Schlesinger
    Commented Mar 16, 2017 at 16:29
5
$\begingroup$

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.

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 Joshua Grochow's answer, but without the added assumption of sampleability.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Samuel Schlesinger
    Commented Mar 17, 2017 at 5:23
  • 1
    $\begingroup$ How can you act in polynomial time if it takes more than polynomial time just to write down a group element? $\endgroup$
    – David Eppstein
    Commented Mar 17, 2017 at 5:26
  • $\begingroup$ 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. $\endgroup$
    – Samuel Schlesinger
    Commented Mar 17, 2017 at 5:34
  • $\begingroup$ That being said, I think that efficient sampleability should confine you to merely exponentially large groups anyways $\endgroup$
    – Samuel Schlesinger
    Commented Mar 17, 2017 at 5:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Commented Mar 17, 2017 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.