Согласно D. den Hertog, «Подход с внутренней точки к линейному, квадратичному и выпуклому программированию», 1994 , линейная программа с переменными, n ограничениями и точностью L разрешима за O ( n 3 L ) времени. Это было улучшено?
25