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 ?

  • 2
    $\begingroup$ Does this answer your question? Relationship between symmetry and computational intractability? $\endgroup$ Nov 19, 2023 at 22:27
  • $\begingroup$ @JoshuaGrochow you linked to the same question twice, was that intended? $\endgroup$ Nov 20, 2023 at 7:41
  • 1
    $\begingroup$ When you say "by adding constraints" you make me think of constraint satisfaction problems, for which there's a very rich theory relating the complexity of the problem with the structure of the "higher endomorphisms" of the problem. Maybe that's what you had read about? $\endgroup$ Nov 20, 2023 at 7:45
  • 1
    $\begingroup$ @DamianoMazza oops that was just a UI error on my phone. I deleted the second one. $\endgroup$ Nov 25, 2023 at 20:54


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.