Erin Catto mentioned in a talk that solving constraints precisely requires cubic time and quadratic space. What algorithm is he talking about when he mentions cubic time?
pdf of slides with following quote:
We can model and program our constraints perfectly. Good enough to drive a robot arm on an assembly line or launch a satellite into space. Unfortunately for games, we do not have enough cycles to solve constraints accurately. Solving constraints precisely requires cubic time and quadratic space. For games we make due with linear time and space, so we are constantly wrestling with our solvers. The better you understand constraint solvers, the better chance you’ll have of creating robust simulations in your game.