Relationship between symmetry and computational intractability?

Question

The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0.

However, If $k(n)=O(\log n)$ then the problem is polynomial time Turing reducible to Graph Isomorphism Problem. If $k(n)=O(\log n/\log \log n)$ then the problem is polynomial time Turing-equivalent to the Graph Automorphism problem which is in $NPI$ and is not known to be $NP$-complete. The Graph Automorphism problem is Turing reducible to the Graph Isomorphism problem.

On the Complexity of Counting the Number of Vertices Moved by Graph Automorphisms, Antoni Lozano and Vijay Raghavan Foundation of Software Technology, LNCS 1530, pp. 295–306

It appears that computational hardness increases as we increase the symmetry of the object we are trying to find (as indicated by the number of nodes that must be moved by the automorphism) . It seems this may explain the lack of polynomial time Turing reduction from the NP-complete version to Graph Automorphism (GA)

Is there another example of a hard problem which supports this relationship between symmetry and hardness?

Answer 1

This isn't exactly the "same" relationship between symmetry and hardness, but there is a close relationship between the symmetries of a Boolean function and its circuit complexity. See:

Babai, L., Beals, R., and Takácsi-Nagy, P. Symmetry and complexity, STOC 1992.

Here's what they show. Let $G_{i} \leq S_{i}$ be a sequence of permutation groups. Let $s(G_{i})$ denote the number of orbits of $G_{i}$ in its induced action on $\{0,1\}^{i}$ (by permutation of the coordinates). Let $\mathcal{F}(G)$ denote the class of languages $L$ such that $L \cap \{0,1\}^{n}$ is invariant under $G_{n}$. Then all languages in $\mathcal{F}(G)$ have circuits of size at most $poly(s(G))$ and depth at most $poly(\log(s(G))$, and this is essentially tight.

---

In the opposite direction, several $NP$ problems whose witness sets have lots of symmetries end up being in $coAM$ (like $GI$), and so are not $NP$-complete unless $PH$ collapses. In fact, the following paper shows that $NP$ problems whose witness sets have lots of symmetries are low for $PP$:

Arvind, V., Vinodchandran, N. V. The counting complexity of group-definable languages. Theoret. Comput. Sci. 242 (2000), no. 1-2, 199--218.

(Note: whether or not "low for $PP$" indicates "unlikely to be $NP$-complete" is a little up in the air, as far as I know. Toda and Ogiwara showed that $PP^{PH} \subseteq BP \cdot PP$. So under the "derandomization" assumption $BP \cdot PP = PP$, $NP$ is in fact low for $PP$, so being low for $PP$ is no obstacle to being $NP$-complete. On the other hand, there is an oracle due to Beigel relative to which $NP$ is not low for $PP$.)

---

In a similar vein as the above, if every polynomial-time decidable equivalence relation has a polynomial-time complete invariant (function $f$ such that $f(x) = f(y)$ iff $x \sim y$), then any $NP$ problem whose witnesses have lots of symmetries reduces to the hidden subgroup problem for the automorphism group of its witnesses. Admittedly, the hypothesis here is rather unlikely to hold, but it does give some connection between symmetry and quantum complexity.

---

Finally, the Mulmuley-Sohoni Geomectric Complexity Theory program is essentially about using symmetry to prove hardness, though the symmetry-hardness connection there is more subtle and less direct.

Answer 2

Structured SAT instances, which do exhibit lots of symmetries, seem easier to solve than random SAT instances. Encoding real world problems into SAT always gives raise to structured instances (which is not surprising, since the real world problems we face do have symmetries). The best complete SAT solvers are able to efficiently solve real world instances with as many as 1,000,000 variables, but none of them, as far as I know, is able to efficiently solve random instances with, say, 10,000 variables (on Edward A. Hirsch homepage it's possible to find some surprisingly small random instances, against which even the best complete SAT solvers get stucked). Thus, from an empirical point of view, the presence of symmetries seems to diminish the hardness.