0
$\begingroup$

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 ?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Does this answer your question? Relationship between symmetry and computational intractability? $\endgroup$
    – Joshua Grochow
    Nov 19 at 22:27
  • $\begingroup$ @JoshuaGrochow you linked to the same question twice, was that intended? $\endgroup$
    – Damiano Mazza
    Nov 20 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$
    – Damiano Mazza
    Nov 20 at 7:45
  • 1
    $\begingroup$ @DamianoMazza oops that was just a UI error on my phone. I deleted the second one. $\endgroup$
    – Joshua Grochow
    Nov 25 at 20:54

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.