Имеет решение и эффективно решается, в чем разница?

Доброго времени суток, хабралюди! Частенько математики останавливаются на существовании решения, и получается что-то подобное.

В гостинице поселились инженер, физик, и математик. У каждого в номере возникает пожар.
Инженер выбегает в коридор, видит на стене пожарный шланг, хватает его, открывает воду, вбегает в номер и заливает очаг возгорания.
Физик, быстро прикинув объем горючих веществ, температуру пламени, теплоемкость воды и пара, атмосферное давление и т.п., наливает в стакан из графина строго определенное количество воды и заливает огонь этой водой.
Математик выскакивает в коридор, видит на стене огнетушитель, и, обрадованно воскликнув: “Решение существует!”, спокойно возвращается в номер.

А о том, какие грабли побадаются на пути «до победного конца», я расскажу под катом.

Воспоминания

Ну, для начала вспомним три «такие» задачи и постараемся в них разобраться.

1. Уравнение n-й степени, при n > 0 имеет n комплексных корней. О том, как эти корни искать в основной теореме алгебры не говорится.
2. Практически любую задачу по геометрии можно решить алгоритмически, т.е. существует алгоритм, который выясняет, истинно ли какое-то геометрическое утверждение, или ложно.
3. Непрерывня функция достигает своих наибольшего и наименьшего значений на компакте (в Евклидовом n-мерном пространстве это ограниченное и замкнутое множество, например в R — это отрезок. А вот интервал уже не замкнут, и например на интервале (0, 1) функция 1/х не принимает своего наибольшего значения).

То есть задачи и правда часто возникают.

Так что в них плохого?

В задаче под номером 1 ничего плохого на данном этапе развития человечества нет. Можно сказать, что мы умеем ее достаточно эффективно решать. Уравнения степеней < 5 разрешимы в радикалах (т.е. можно найти точные значения корней). Доказано, что уравнения степеней > 4 не разрешимы в радикалах (а именно, приведены конкретные уравнения, которые нельзя решить), для этого используются группы Галуа. Но бывает так, что нам все-таки нужно найти корни уравнения, например 100-й степени. А вот это уже умеют решать алгоритмически, а именно — искать все корни со сколь угодно большой точностью. Если кто не верит — wolframalpha.com.

Задача номер 2 чуточку интереснее. Вообще говоря, это следствие теоремы Тарского – Зайденберга. Доказательство ее простое, его можно рассказывать хоть школьникам, которые умеют брать производную многочлена и делить многочлены столбиком. Если вкратце и по-простому, то суть теоремы в том, что из любого выражения про многочлены в действительных числах можно убрать кванторы («существует х», «для любого х»).
Например выражение: «существует х, что x^2 + px + q = 0». Т.е. у нас спрашивается, когда подобное квадратное уравнение имеет корни. Это мы знаем, когда p^2 — 4q >= 0 (заметим, что тут квантора уже нет!). Идея теоремы в том, что можно написать алгоритм, который за нас бы это выяснял, причем степень не важна.
Как это связано с геометрией? А вот как, практически любое утверждение можно записать введя систему координат и навесив кучу кванторов. Идея в том, что когда мы «убиваем» квантор, у нас уходит одна переменная. А когда у нас не останется переменных, то мы получим выражение вида 5 > 3, об истинности которого мы уже все знаем.
Пфф, так получается, что геометрия — тривиальная наука? Есть алгоритм, который бы выяснял: верно утверждение, или ложно. Наверное, так и подумали некоторые математики, но не все так просто. Если мы рассмотрим пример с x^2 + px + q = 0, то чтобы «убить» один квантор, нам понадобится достаточно большое количество шагов. А чтобы уже подобным способом доказать какую-то содержательную геометрическую теорему, понадобится время, сравнимое со временем существования Земли.
Но может мы решаем как-то неправильно? На самом деле доказано, что нет эффективного алгоритма, решающего эту задачу.
Ура, геометрия не тривиальна. Фух, разобрались. Едем дальше.

Задача 3, как все было

Тут расскажу маленькую предысторию. Вообще, математика — достаточно абстрактная наука, посему летом я решил позаниматься финансами и прошел онлайн курс на coursera.org. Там тщательно разбирались акции, что да как. Но преподаватель часто говорил, что тут всегда выбор, либо у тебя большой риск и большой доход, либо мальникй риск и низкий доход. Мне стало интересно, а есть ли золотая середина? Можно ли из N компаний выбрать акции так, чтобы у тебя был маленкий риск и большой доход? Неплохо бы еще написать алгоритм по решению этой задачи. Формулировка ясна, теперь детали.

Человеку не сведующему в данном деле покажется, что у рисков зависимость линейная, у дохода линейная — и чего тут вообще решать? Как бы не так, риски считаются более хитрым способом, ибо компании друг с другом взаимосвязаны. Благо, что итоговый риск считается, как многочлен второй степени, но конечно же от N переменных, где N — число компаний.
Окей, как теперь связать риски и доходы? Если риск например 5%, а доход 100$ это лучше, чем риск 10%, а доход 150$, или хуже? Грубо говоря, можно посчитать средний риск, например 10%, средний доход, например 200$ и приравнять 1 процент риска к 20$ (200 / 10). Эм, и что нам это дало? А вот что — пусть у нас есть N компаний. Долевые соотношения акций — x1, x2, …, xN. Тогда риск считается как некоторый многочлен (каждый моном которого не больше второй степени), а доход считается линейно. Возьмем и вычтем одно уравнение из другого, домножив на поправочный коэффициент (Доход с "+", риск с "-"). Это и будет итоговая формула, у которой нужно найти максимум. Кстати у нас есть ограничение, что x1 + x2 +… + xN = 1, x1 >0, …, xN > 0.

Теперь постараемся проанализировать задачку. Мне, как математику, в голову сразу пришла идея рассмотреть N-мерное пространство, там у нас есть компакт, задаваемый вот так x1 + x2 +… + xN = 1, x1 > 0, …, xN > 0 и многочлен второй степени. Пфф, да все элементарно — подумал я. Мы знаем, что на компакте уравнение принимает наибольшее значение, причем либо градиент в этой точке нулевой, либо максимум лежит на границе, т.е. нужно проверить и то и то. С этими мыслями я откинул задачу где-то на месяц. Но что-то не оставляло в покое. Вот выдалось свободное время, было взято произвольное уравнение, бумага и ручка. Оппа — да мое решение работает за (N!) — факториал. Если его реализовать на компьютере, то для 100 компаний это будет работать много больше времени существования Солнечной системы. Краткие объяснения: когда мы проверяем границы компакта, мы переходим от N-мерного простарнства к N штукам (N-1)-мерных пространств. Ужасно — подумал я, но надежды решить задачу не потерял.

Походив среди умных математиков и поспрашивая их, я узнал о методе множителей Лагрнажа для неравенств (мы проходили лишь для уравнений). И вот он как раз решает эту задачу эффективно. Можете почитать немного на википедии.

Не останавливайтесь на существовании решения, а идите до конца. Удачи вам :).
Спасибо за прочтение!