<p>I read once that the more a problem has some symmetries the &quot;easier&quot; it is to solve and in particular its (time) complexity is polynomial.</p>
<p>Conversely, when starting from a polynomial problem, if you break its symmetries, as an example by adding constraints, its complexity soon becomes exponential or at least no more in P.</p>
<p>Do you know some examples of this ? I wonder also if I could find a more thorough description, for any kind of problem, of the relationship between its symmetries and its complexity ?</p>

CC BY-SA 4.0
2023-11-19T22:27:49.713Z
Does this answer your question? [Relationship between symmetry and computational intractability?](https://cstheory.stackexchange.com/questions/871/relationship-between-symmetry-and-computational-intractability)
Joshua Grochow
CC BY-SA 4.0
2023-11-20T07:41:55.967Z
@JoshuaGrochow you linked to the same question twice, was that intended?
Damiano Mazza
CC BY-SA 4.0
2023-11-20T07:45:47.627Z
When you say "by adding constraints" you make me think of constraint satisfaction problems, for which there's a [very rich theory](https://www.karlin.mff.cuni.cz/~barto/Articles/SurveyBSLverSub.pdf) relating the complexity of the problem with the structure of the "higher endomorphisms" of the problem.  Maybe that's what you had read about?
Damiano Mazza
CC BY-SA 4.0
2023-11-25T20:54:47.823Z
@DamianoMazza oops that was just a UI error on my phone. I deleted the second one.
Joshua Grochow
<time-complexity><symmetry>
Relationships between problem symmetry and its complexity
deb2014
# Relationships between problem symmetry and its complexity

(Asked by: username_0 on 2023-11-19)

I read once that the more a problem has some symmetries the "easier" it is to solve and in particular its (time) complexity is polynomial.

Conversely, when starting from a polynomial problem, if you break its symmetries, as an example by adding constraints, its complexity soon becomes exponential or at least no more in P.

Do you know some examples of this ? I wonder also if I could find a more thorough description, for any kind of problem, of the relationship between its symmetries and its complexity ?

**Tags:** time-complexity, symmetry
> **Comments:**
> **username_1**: Does this answer your question? [Relationship between symmetry and computational intractability?](https://cstheory.stackexchange.com/questions/871/relationship-between-symmetry-and-computational-intractability)  
> **username_2**: @JoshuaGrochow you linked to the same question twice, was that intended?  
> **username_2**: When you say "by adding constraints" you make me think of constraint satisfaction problems, for which there's a [very rich theory](https://www.karlin.mff.cuni.cz/~barto/Articles/SurveyBSLverSub.pdf) relating the complexity of the problem with the structure of the "higher endomorphisms" of the problem.  Maybe that's what you had read about?  
> **username_1**: @DamianoMazza oops that was just a UI error on my phone. I deleted the second one.  

---

## 0 answers

