Мы знаем, что линейные программы (ЛП) могут быть решены точно за полиномиальное время с помощью метода эллипсоидов или метода внутренних точек, таких как алгоритм Кармаркара. Некоторые ЛП с суперполиномиальным (экспоненциальным) числом переменных / ограничений также могут быть решены за...