<p>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 <a href="http://logic.pdmi.ras.ru/~hirsch/sat.html" rel="nofollow">Edward A. Hirsch homepage</a> 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.</p>

CC BY-SA 2.5
2010-09-08T12:11:23.830Z
2010-11-05T11:04:16.560Z
2010-11-05T11:04:16.560Z
Giorgio Camerani
<p>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:</p>

<blockquote>
  <p>Babai, L., Beals, R., and Takácsi-Nagy, P.  <a href="http://doi.acm.org/10.1145/129712.129754">Symmetry and complexity</a>, STOC 1992.</p>
</blockquote>

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

<hr>

<p>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$:</p>

<blockquote>
  <p>Arvind, V., Vinodchandran, N. V. <a href="http://dx.doi.org/10.1016/S0304-3975(98)00218-7">The counting complexity of group-definable languages</a>. Theoret. Comput. Sci. 242 (2000), no. 1-2, 199--218.</p>
</blockquote>

<p>(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. <a href="http://dx.doi.org/10.1137/0221023">Toda and Ogiwara</a> 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 <a href="http://dx.doi.org/10.1007/BF01263422">Beigel</a> relative to which $NP$ is not low for $PP$.)</p>

<hr>

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

<hr>

<p>Finally, the Mulmuley-Sohoni <a href="http://ramakrishnadas.cs.uchicago.edu/">Geomectric Complexity Theory</a> program is essentially about using symmetry to prove hardness, though the symmetry-hardness connection there is more subtle and less direct.</p>

CC BY-SA 2.5
2010-09-02T16:08:19.060Z
2010-09-02T16:22:06.153Z
2010-09-02T16:22:06.153Z
Joshua Grochow
<p>The <span class="math-container">$k$</span>-fixed point free automorphism problem asks for  a graph automorphism which moves at least <span class="math-container">$k(n)$</span> nodes. The problem is <span class="math-container">$NP$</span>-complete if <span class="math-container">$k(n)=n^c$</span> for any <span class="math-container">$c$</span>&gt;0.</p>
<p>However, If <span class="math-container">$k(n)=O(\log n)$</span> then the problem is polynomial time Turing reducible to Graph Isomorphism Problem. If <span class="math-container">$k(n)=O(\log n/\log \log n)$</span> then the problem is polynomial time Turing-equivalent to the Graph Automorphism problem which is in <span class="math-container">$NPI$</span> and is not known to be <span class="math-container">$NP$</span>-complete. The Graph Automorphism problem is Turing reducible to the Graph Isomorphism problem.</p>
<p><a href="https://doi.org/10.1007%2F978-3-540-49382-2_28?from=SL" rel="nofollow noreferrer">On the Complexity of Counting the Number of Vertices Moved by Graph Automorphisms,
Antoni Lozano and Vijay Raghavan
</a>
<a href="https://doi.org/10.1007%2F978-3-540-49382-2_28?from=SL" rel="nofollow noreferrer">Foundation of Software Technology, LNCS 1530, pp. 295–306</a></p>
<p>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)</p>
<blockquote>
<p>Is there another example of a hard problem which supports this relationship between symmetry and hardness?</p>
</blockquote>

CC BY-SA 3.0
2012-09-08T16:58:38.717Z
see also the Berman-Hartmanis isomorphism conjecture for one of the strongest symmetries conjectured although _caveat_ conventional wisdom is against it
vzn
CC BY-SA 2.5
2010-09-02T12:28:17.553Z
Please add a reference to the NP-completness result for k-fixed point free automorphism. Thanks.
Martin Schwarz
CC BY-SA 2.5
2010-09-02T15:56:07.847Z
Graph Automorphism is not known to be in NPI.
Emil
CC BY-SA 2.5
2010-09-02T16:10:41.430Z
@Emil: Nothing is *known* to be in NPI, since we don't know $P \neq NP$!  But GA, like GI, is not NP-complete unless PH collapses.  OTOH, we don't really have any reason to think it is not in P, other than that people have tried and failed.
Joshua Grochow
CC BY-SA 2.5
2010-09-02T16:11:07.310Z
@turkistany: Great question!
Joshua Grochow
CC BY-SA 2.5
2010-09-02T16:19:25.960Z
@Joshua: Yes I know. I was just suggesting a correction for the question text.
Emil
CC BY-SA 2.5
2010-09-02T16:23:55.853Z
@Emil: Ah. I am so used to people saying "in NPI" and meaning "probably in NPI" that I didn't even notice.  But you are correct, of course.
Joshua Grochow
CC BY-SA 2.5
2010-09-02T16:40:18.597Z
@Joshua, It seems tuning the growth rate of $k(n)$ covers the complexity spectrum from $P$ to $NP$-complete.
Mohammad Al-Turkistany
<cc.complexity-theory><graph-isomorphism><automorphism><symmetry>
Relationship between symmetry and computational intractability?
Mohammad Al-Turkistany
# Relationship between symmetry and computational intractability?

(Asked by: username_0 on 2010-09-02)

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](https://doi.org/10.1007%2F978-3-540-49382-2_28?from=SL)
[Foundation of Software Technology, LNCS 1530, pp. 295–306](https://doi.org/10.1007%2F978-3-540-49382-2_28?from=SL)

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?

**Tags:** cc.complexity-theory, graph-isomorphism, automorphism, symmetry

> **Comments:**
> **username_2**: Please add a reference to the NP-completness result for k-fixed point free automorphism. Thanks.  
> **username_3**: Graph Automorphism is not known to be in NPI.  
> **username_4**: @username_3: Nothing is *known* to be in NPI, since we don't know $P \neq NP$!  But GA, like GI, is not NP-complete unless PH collapses.  OTOH, we don't really have any reason to think it is not in P, other than that people have tried and failed.  
> **username_4**: @turkistany: Great question!  
> **username_3**: @Joshua: Yes I know. I was just suggesting a correction for the question text.  
> **username_4**: @username_3: Ah. I am so used to people saying "in NPI" and meaning "probably in NPI" that I didn't even notice.  But you are correct, of course.  
> **username_0**: @Joshua, It seems tuning the growth rate of $k(n)$ covers the complexity spectrum from $P$ to $NP$-complete.  
> **username_1**: see also the Berman-Hartmanis isomorphism conjecture for one of the strongest symmetries conjectured although _caveat_ conventional wisdom is against it  

---

## 2 answers

### Answer by username_4 on 2010-09-02. Score: 17 | Accepted answer

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](http://doi.acm.org/10.1145/129712.129754), 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](http://dx.doi.org/10.1016/S0304-3975(98)00218-7). 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](http://dx.doi.org/10.1137/0221023) 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](http://dx.doi.org/10.1007/BF01263422) 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](http://ramakrishnadas.cs.uchicago.edu/) program is essentially about using symmetry to prove hardness, though the symmetry-hardness connection there is more subtle and less direct.


---

### Answer by username_5 on 2010-09-08. Score: 3

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](http://logic.pdmi.ras.ru/~hirsch/sat.html) 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.


---

