Симплекс-метод, разработанный Джорджем Данцигом в 1947 году, превосходно и быстро решал 99 процентов промышленных задач линейного программирования (ЛП). Однако в 1972 году математики Виктор Кли и Джордж Минти сконструировали искусственный многогранник (Куб Кли-Минти), на котором симплекс-метод был вынужден обойти абсолютно все вершины, что требовало экспоненциального времени вычислений. Это породило главную интригу дискретной математики XX века: относится ли линейное программирование к классу задач $P$ (решаемых за полиномиальное время)? В 1979 году советский математик Леонид Хачиян потряс мировой научный мир, опубликовав Метод эллипсоидов, навсегда доказавший, что линейное программирование строго полиномиально.