For linear programing, the interior point method has a polynomial worst case. It also not probabilistic, so linear programing is not rely a good example
For linear programing, the interior point method has a polynomial worst case. It also not probabilistic, so linear programing is not rely a good example