The 2024 Developer Survey results are live! See the results

# Tag Info

## Hot answers tagged symmetry

Accepted

### Are There Highly Symmetric NP- or P-complete Languages?

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-...
• 37.8k

### Are There Highly Symmetric NP- or P-complete Languages?

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 ...
• 51.1k
Accepted

### Computing the edge orbits of a graph (and discussing definitions)

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 ...
• 3,392
Accepted

### Is $GCT$ necessarily a negative result program?

It depends a little what you mean exactly by "GCT". If you mean it more generally, the answer is certainly yes. If you mean it more specifically about multiplicity obstructions, this is a ...
• 37.8k
Accepted

### What is the probability that a random Boolean function has a trivial automorphism group?

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)$, ...
• 37.8k

### Computing the edge orbits of a graph (and discussing definitions)

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 ...
• 37.8k
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\}$ ...