12
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}$ ...
answered Mar 16 '17 at 16:27
Joshua Grochow
33.7k44 gold badges115115 silver badges205205 bronze badges
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.
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 ...
answered Mar 17 '17 at 5:15
David Eppstein
49.2k33 gold badges160160 silver badges269269 bronze badges
4
It turns out that yes, indeed, there are two possible definitions for edge-automorphisms... but it turns out that they almost always coincide so that it seems that people often get away with not making the distinction.
First, some notation. For a simple graph $G = (V,E)$ we let $\Gamma_V(G)$ define the group of automorpisms over the set of vertices $V$ ...
4
Yes. To your first question, the probability goes to zero double-exponentially fast. This can be calculated as follows. For each permutation $\pi$, we can bound the probability that $\pi \in Aut(f)$, i.e. that $f(\pi(x)) = f(x)$ for all $x \in \{0,1\}^n$. Consider the orbits of $\pi$ acting on $\{0,1\}^n$. We have that $\pi$ is an automorphism of $f$ iff $f$ ...
answered Jan 25 '18 at 9:08
Joshua Grochow
33.7k44 gold badges115115 silver badges205205 bronze badges
2
If $p$ is fixed, graph isomorphism can be tested in polynomial time, see [E. Luks. Isomorphism of graphs of bounded valance can be tested in polynomial time. Journal of Computer and System Sciences, 25:42–65, 1982].
2
They are equivalent. For any $x$, let $g_x$ be a permutation with just two cycles: one consisting of $\{i \in [n] : x_i = 0\}$ (say, in ascending order) and one consisting of $\{i \in [n] : x_i = 1\}$ (also in ascending order). Then the "GC" description is just $01enc(g)$, whose length is $2 + K(g)$. But $K(g) \leq K(x) + O(1)$, since the above description ...
answered Feb 2 '18 at 8:32
Joshua Grochow
33.7k44 gold badges115115 silver badges205205 bronze badges
1
Your problem is equivalent to Graph Isomorphism under polynomial-time reductions, even if you include edge colors.
First, GI is equivalent (under polynomial-time Turing reductions) to computing generators of the automorphism group. From those generators it is easy (using standard permutation group machinery) to compute the edge orbits in polynomial time.
...
answered Oct 22 '19 at 19:33
Joshua Grochow
33.7k44 gold badges115115 silver badges205205 bronze badges
Only top voted, non community-wiki answers of a minimum length are eligible
Related Tags
symmetry × 15cc.complexity-theory × 6
graph-theory × 4
sat × 3
permutations × 3
gr.group-theory × 3
automorphism × 3
co.combinatorics × 2
randomness × 2
graph-isomorphism × 2
algebra × 2
ds.algorithms × 1
graph-algorithms × 1
optimization × 1
time-complexity × 1
boolean-functions × 1
reductions × 1
np-complete × 1
np × 1
graph-colouring × 1
kolmogorov-complexity × 1
complexity × 1
structural-complexity × 1
gct × 1