There are cases where the symmetries of a problem ( seem to ) characterize its complexity. One very interesting example is constraint satisfaction problems (CSPs).
Definition of CSP
A CSP is given by a domain $U$, and a constraint language $\Gamma$ ($k$-ary functions from $U^k$ to $\{0, 1\}$). A constraint satisfaction instance is given by a set of variables $V$ and constraints from $\Gamma$. A solution to the instance is an assignment $\phi:V \rightarrow U$ such that all constraints are satisfied.
For example, in this language 3-SAT is given by $\Gamma$ which is the set of all disjunctions of 3 literals, $U$ is simply $\{0, 1\}$. For another example, systems of linear equations mod 2 are given by a $\Gamma$ which is all linear equations mod 2 with $k$ variables, and $U$ is again $\{0, 1\}$.
Polymorphisms
There is a sense in which the hardness of a CSP is characterized by its symmetries. The symmetries in question are called polymorphisms. A polymorphism is a way to locally combine several solutions to a CSP to get a new solution. Locally here means that there is a function that is applied to each variable separately. More precisely, if you have several solutions (satisfying assignments) $\phi_1, \ldots, \phi_t$, a polymorphism is a function $f:U^t \rightarrow U$ that can be applied to each variable to get a new solution $\phi$: $\phi(v) = f(\phi_1(v), \ldots, \phi_t(v))$. For $f$ to be a polymorphism it should map all tuples of $t$ satisfying assignments to any instance to a satisfying assignment of the same instance.
A polymorphism for systems of linear equations for example is $f(x, y, z) = x + y + z \pmod 2$. Notice that $f(x, x, y) = f(y, x, x) = y$. An $f$ that satisfies this property is known as a Maltsev operation. CSPs that have a Maltsev polymorphism are solvable by Gaussian elimination.
On the other hand, disjunctions of 3 literals only have dictators as polymorphisms, i.e. functions of the type $f(x, y) = x$.
Polymorphisms and Complexity (the dichotomy conjecture)
Polymorphisms in fact have computational implications: if a CSP $\Gamma_1$ admits all polymorphisms of $\Gamma_2$, then $\Gamma_1$ is polynomial-time reducible to $\Gamma_2$. This is a way to formally say that a CSP $\Gamma_2$ which is "less symmetric" than another CSP $\Gamma_1$ is in fact harder.
A major open problem in complexity theory is to characterize the hardness of CSPs. The dichotomy conjecture of Feder and Vardi states that any CSP is either in P or NP-complete. The conjecture can be reduced to a statement about polymorphisms: a CSP is NP-hard if and only if the only polymorphisms it admits are "dictators" (otherwise it is in P). I.e. a CSP is hard only if there is no local way to form genuine new solutions from old solutions. The if part (hardness) is known, but the only if part (designing a polytime algorithm) is open.
However, an important case where we do have a dichotomy is boolean CSPs (where $U = \{0, 1\}$). According to Schaefer's theorem, a boolean CSP is in P if it admits one of 6 polymorphisms, otherwise it is NP-complete. The six polymorphisms are basically what you need to solve the problem either by gaussian elimination or by propagation (as you do with horn-sat for example), or to solve it by a trivial assignment.
To read more about polymorphisms, universal algebra, and the dichotomy conjecture, you can look at the survey by Bulatov.
Polymorphisms and Approximability
I also recommend an IAS lecture by Prasad Raghavendra where he puts his result giving optimal approximability of any CSP assuming the unique games conjecture in a similar framework. On a high level, if all polymorphisms (this needs to be generalized to handle approximation problems) of a CSP are close to dictators, one can use the CSP to design a way to test if a function is a dictator, and that turns out to be all you need in order to give a hardness of approximation reduction from unique games. This gives the hardness direction of his result; the algorithmic direction is that when a CSP has a polymorphism which is far from a dictator, one can use an invariance principle (generalization of central limit theorems) to argue that an SDP rounding algorithm gives a good approximation. A really sketchy intuition for the algorithmic part: a polymorphism that is far from a dictator doesn't care if it is given as arguments (a distribution over) variable assignments or gaussian random variables that locally approximate a distribution over variable assignments. This is the same way that a sum function "doesn't care" if it is given discrete random variables with small variance or gaussian r.v.'s with the same variance, by the central limit theorem. The gaussian random variables we need can be computed from an SDP relaxation of the CSP problem. So we find a polymorphism that is far from a dictator, feed it the gaussian samples, and get a good solution back.
