Начало тут 👆

📚 В этом канале и на стримах (тут и тут) мы уже не раз обсуждали фундаментальные вопросы вычислительной сложности:

Что такое классы P и NP:
- Почему вопрос "P = NP?" — один из величайших нерешённых в математике?
- И что вообще значит «решить задачу за полиномиальное время»?

Теперь давайте посмотрим на задачу, которая стала поворотной точкой между прикладной оптимизацией и теоретической информатикой.
Речь о линейном программировании (или линейной оптимизации) — и прорыве, который произошёл в 1979 году.

🔧 Что такое линейная оптимизация?
Это класс задач, где нужно оптимизировать линейную функцию при наличии линейных ограничений.
То есть: что-то максимизировать или минимизировать, соблюдая заданные условия.

💡 Пример:
Составить рацион питания из доступных продуктов — так, чтобы:
-покрыть все суточные нормы по питательным веществам (ограничения),
- но потратить как можно меньше денег (целевая функция).

С 1947 года такие задачи эффективно решались с помощью симплекс-метода — разработанного Джорджем Данцигом.

📈 На практике метод довольно хорош: миллионы логистических, экономических и инженерных систем полагались (и полагаются) на симплекс.

Но была проблема:
⚠️ в теории симплекс может работать экспоненциально долго. А значит, мы не знали, принадлежит ли линейная оптимизация к классу P (полиномиально вычислимых задач).

💥 1979: появляется Хачиян

И вот, в 1979 году Леонид Хачиян, молодой математик из СССР, предлагает эллипсоидный метод — первый алгоритм, который решает задачу линейного программирования за гарантированное полиномиальное время.

🌀 Идея метода:

начать с большого эллипсоида, содержащего все возможные решения, постепенно сжимать его, отсекая "плохие" части, пока не останется область, содержащая оптимум.

📉 Но на практике метод оказался медленным (см. сноску внизу 🍒). А вот в теории он дал главное:

🔐 Он доказал, что линейная оптимизация ∈ P.
То есть: существует "быстрый алгоритм" (см. сноску внизу 🍒).

🧩 А теперь — мост к комплексити-теории
Вот почему это открытие было настолько важно:

До Хачияна не было известно, попадает ли линейная оптимизация в класс P.

Его работа замкнула круг между прикладной задачей и теоретическим анализом.

Она показала, что не всякая полезная задача сложна. Некоторые — фундаментально решаемы эффективно (см. сноску внизу 🍒).

А ещё — это вдохновило целую волну исследований:
📈 появились внутренние точечные методы (например, метод Кармаркара), которые были не только полиномиальными, но и быстрыми на практике.

📌 Итог
Линейное программирование — редкий случай задачи, которая:
- 🔧 реальная прикладная задача,
- ✅ и точно в классе P.

Да, в реальной жизни симплекс чаще всего быстрее,
но именно эллипсоид Хачияна навсегда изменил теоретическое понимание линейной оптимизации.

🧠 А теперь — маленькая

загадка:
Как так получается,
что теоретически «быстрый» эллипсоид на практике
почти всегда проигрывает по времени
теоретически «медленному» симплексу?

📌 Подумайте:
метод эллипсоида и полиномиальное время — это гарантия на худший случай, а не обещание быть быстрым всегда.

А симплекс?
Возможно, во многих случаях он просто умеет "угадывать", где находится решение — даже если не обещает ничего формально для всех случаев (см. сноску внизу 🍒).

👉 И в этом — вся красота прикладной математики.
И вся хитрость теории сложности.

@easy_about_complex

#P #NP #PvsNP #LinearProgramming
_

🍒 сноска: есть нюансы! По сути эллипсоидный метод требует полиномиального времени с очень высокой степенью полиномов. Это значит, что эллипсоидный метод Хачияна начнёт бить симплекс-метод по времени вычислений на практике только начиная с какого-то определённого размера оптимизационной задачи и выше? (worst case ✅ average case❓). Вот с каких порядков задачи симплекс-метод начнёт уступать методу эллипсоидов - я сейчас не могу сказать. Надо разбираться в деталях. Я слышал(?), что в в последние годы в больших вычислительных центрах, где реально большие задачи эллипсоид таки бьёт симплекс (worst case?average case?practical cases?). Но это не точно.