Я занимаюсь квантовой химией, и раньше занимался близкой ей по задачам газовой электронографией. У нас электронографисты любят фразу “квантовики решают прямую задачу, а мы обратную”. Эта фраза мне понятна: расчёт изначально находит структуру, а в электронографии структура определяется через МНК (градиентный спуск) по экспериментальным данным.
В действительности же, по-моему, любые задачи в математике в той или иной степени обратные, и вообще вся математика посвящена решению обратных задач. Возьмём для примера пять уравнений:
1) ax+b=0
2) ax^2+bx+c=0
3) ax^3+bx^2+cx+d=0
4) ax^4+bx^3+cx^2+dx+e=0
5) ax^5+bx^4+cx^3+dx^2+ex+f=0
Чтобы решить первую задачу, нужно провести одно деление. Вторая задача решается через детерминант (я всё не могу найти, как называется эта формула – формула Виета?). Третья задача решается по формуле Кардано, чётвёртая, если не ошибаюсь, решается очень похожим образом (через резольвенты), а пятая в общем случае “не решается”, точнее её нельзя решить аналитически.
По сути, все пять задач – это обратные задачи от простого уравнения n-й степени. Т.е. если мы пишем, например, y=ax^2+b+c, то нахождение y по известному x – это прямая задача, а нахождение x по известному y – это обратная задача.
Признаки прямой задачи:
1) Её можно решить в любом интервале x;
2) Для любого x решение единственно;
3) Решение относительно простое по сравнению с обратной задачей
4) Сложность (время) и надёжность решения прямой задачи практически не зависит от того, чему равен x или какое было начальное приближение.
5) Ещё одна связь между прямой и обратной задачей: существуют очень простые и универсальные методы решения обратной задачи через прямую, например простой перебор или градиентный спуск. Хотя они обычно далеко не эффективны в плане требуемых ресурсов.

Теперь я предлагаю такую идею: взять пять уравнений выше и определить их сложность. Сложность решения задачи можно измерить количественно – количеством машинного времени, потраченного на её решение с применением наилучшего алгоритма.
У меня сильное подозрение, что для первых четырёх задач сложность будет описываться некой простой зависимостью от номера (например, экспонентой), а для пятой сложность будет явно выпадать из этой зависимости. И из этого можно будет заключить, что в математике есть нерешённая задача – найти “сверхформулу Кардано”, которая позволит решить пятое уравнение аналитически.
Сложность прямой задачи для этих четырёх уравнений тоже растёт, хотя не очень сильно. И возникает ещё одна идея: как сложность обратной задачи в общем случае зависит от сложности прямой. Я подозреваю, что эта зависимость, может быть, экспоненциальная.
В программировании все эти термины, как я понимаю, тоже вполне применимы. Достаточно понятный пример – нейросети: работа нейросети – это решение прямой задачи, а тренировка нейросети – решение обратной.
По-моему, вся математика и всё computer science так или иначе сводится к оптимальным способам решения обратных задач. И тут можно развить тему для программистов. Я прихожу к выводу, что при программировании сложных алгоритмов полезно применять “тяжёлые ассерты”: это такие ассерты, которые проверяют всё сразу. Эти ассерты довольно легко реализовать, но они сильно тормозят работу программу, поэтому их нужно отключать даже не только в финальном билде программы, но и вообще почти всегда, за исключением моментов когда нужно проверить критические участки алгоритма. С тяжёлыми ассертами баги должны легко выявляться. Так вот это всё тоже входит в изначальную тему: ассерты – это тоже вспомогательное решение прямой задачи, позволяющее проверить насколько корректно решается обратная.

Здравствуйте, Khimik, Вы писали:

K>Сложность решения задачи можно измерить количественно – количеством машинного времени, потраченного на её решение с применением наилучшего алгоритма.
И как вы собираетесь искать наилучший алгоритм? Не говоря уже о количестве машинного времении которое зависит от реализации, платформы и входных данных.

K>По-моему, вся математика и всё computer science так или иначе сводится к оптимальным способам решения обратных задач.
Есть еще сопряженные задачи, приближенные решения, и смена представления (всякие интегральные преобразования) и много чего интересного
Вопрос-то в чем?

Здравствуйте, Khimik, Вы писали:

K>В действительности же, по-моему, любые задачи в математике в той или иной степени обратные, и вообще вся математика посвящена решению обратных задач. Возьмём для примера пять уравнений:
K>1) ax+b=0
K>2) ax^2+bx+c=0
K>3) ax^3+bx^2+cx+d=0
K>4) ax^4+bx^3+cx^2+dx+e=0
K>5) ax^5+bx^4+cx^3+dx^2+ex+f=0

K>По сути, все пять задач – это обратные задачи от простого уравнения n-й степени. Т.е. если мы пишем, например, y=ax^2+b+c, то нахождение y по известному x – это прямая задача, а нахождение x по известному y – это обратная задача.
Откуда выплыл y?
Уравнение: a₀xⁿ+a₁x^n-1+...+a_ix^n-i+...+a_n-1x+a_n=0, нет никакого y .
Тут прямая задача — нахождение Х, а обратная определение вектора коэффициентов А по известному вектору Х.

K>Признаки прямой задачи:
На пальцах:
Прямая задача: известно, что было, надо найти, что стало.
Обратная задача: известно, что стало, надо найти, что было.

Здравствуйте, Dym On, Вы писали:

K>>Признаки прямой задачи:
DO>На пальцах:
DO>Прямая задача: известно, что было, надо найти, что стало.
DO>Обратная задача: известно, что стало, надо найти, что было.

Тут интересно то, что в природе (более того — в математике) так устроено, что для некоторых задач "обратные" решаются легко (класс P), а для других крайне сложно (класс NP) или даже не решаются вообще (решение неизвестно, только приблизительно подбором и т.п.).

Почему так? В чем тайная причина этой асимметрии?
Тайна сия велика есть.

Здравствуйте, anonymouse2, Вы писали:

A>Тут интересно то, что в природе (более того — в математике) так устроено, что для некоторых задач "обратные" решаются легко (класс P), а для других крайне сложно (класс NP) или даже не решаются вообще (решение неизвестно, только приблизительно подбором и т.п.).

A>Почему так? В чем тайная причина этой асимметрии?
A>Тайна сия велика есть.

Посмотри на мясо, мясорубку и фарш. Или, если хочется совсем уж природного, без ГМО — посмотри на овёс, лошадь и навоз. Интуитивно понятно, что фарш обратно не провернешь, и если навоз прогнать через лошадь в обратном направлении, овса не получишь.

Здравствуйте, Sharowarsheg, Вы писали:

S>Посмотри на мясо, мясорубку и фарш. Или, если хочется совсем уж природного, без ГМО — посмотри на овёс, лошадь и навоз. Интуитивно понятно, что фарш обратно не провернешь, и если навоз прогнать через лошадь в обратном направлении, овса не получишь.

Это разумеется все так, но вопрос был не об этом.

Здравствуйте, anonymouse2, Вы писали:

S>>Посмотри на мясо, мясорубку и фарш. Или, если хочется совсем уж природного, без ГМО — посмотри на овёс, лошадь и навоз. Интуитивно понятно, что фарш обратно не провернешь, и если навоз прогнать через лошадь в обратном направлении, овса не получишь.

A>Это разумеется все так, но вопрос был не об этом.

Тогда непонятно, о чём вопрос.

Тут интересно то, что в природе (более того — в математике) так устроено, что для некоторых задач "обратные" решаются легко (класс P), а для других крайне сложно (класс NP) или даже не решаются вообще (решение неизвестно, только приблизительно подбором и т.п.).

Да, так устроено, что получить бесполезное дерьмо можно бесчисленным множеством разных способов, а получить полезный овёс можно малым числом сложных способов. При этом полезность субъективна, естественно. Математика вообще не имеет ни прямых, ни обратных задач. Это ты субъективно определяешь, какое направление прямое, а какое обратное.

Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, Khimik, Вы писали:

K>>Сложность решения задачи можно измерить количественно – количеством машинного времени, потраченного на её решение с применением наилучшего алгоритма.
_>И как вы собираетесь искать наилучший алгоритм? Не говоря уже о количестве машинного времении которое зависит от реализации, платформы и входных данных.

Наилучший на данный момент алгоритм. Тут надо спрашивать знающих математиков.

K>>Признаки прямой задачи:
DO>На пальцах:
DO>Прямая задача: известно, что было, надо найти, что стало.
DO>Обратная задача: известно, что стало, надо найти, что было.

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

S>Посмотри на мясо, мясорубку и фарш. Или, если хочется совсем уж природного, без ГМО — посмотри на овёс, лошадь и навоз. Интуитивно понятно, что фарш обратно не провернешь, и если навоз прогнать через лошадь в обратном направлении, овса не получишь.

Это слишком далёкая аналогия. Вот гораздо более корректная: классической "холодно-горячо" (решение обратной задачи методом градиентного спуска).

Здравствуйте, Khimik, Вы писали:


S>>Посмотри на мясо, мясорубку и фарш. Или, если хочется совсем уж природного, без ГМО — посмотри на овёс, лошадь и навоз. Интуитивно понятно, что фарш обратно не провернешь, и если навоз прогнать через лошадь в обратном направлении, овса не получишь.

K>Это слишком далёкая аналогия. Вот гораздо более корректная: классической "холодно-горячо" (решение обратной задачи методом градиентного спуска).

Как ты определил, какая задача обратная? В случае лошади, овса и навоза это более-менее понятно, а вот в случае горячо-холодно, какая задача обратная?

Здравствуйте, Khimik, Вы писали:

K>Короче, решить прямую задачу — значит перемещаться из прошлого в будущее, решить обратную задачу — перемещаться из будущего в прошлое.

В математике нет времени, а так всё хорошо.

Здравствуйте, Sharowarsheg, Вы писали:

S>Да, так устроено, что получить бесполезное дерьмо можно бесчисленным множеством разных способов, а получить полезный овёс можно малым числом сложных способов. При этом полезность субъективна, естественно. Математика вообще не имеет ни прямых, ни обратных задач. Это ты субъективно определяешь, какое направление прямое, а какое обратное.

Интересно как минимум почему так устроено, и как бы выглядел мир если бы было устроено иначе (в нашем мире скорее всего P!=NP, и интересно как бы был устроен мир в котором P=NP).

Здравствуйте, Khimik, Вы писали:

K>У меня сильное подозрение, что для первых четырёх задач сложность будет описываться некой простой зависимостью от номера (например, экспонентой), а для пятой сложность будет явно выпадать из этой зависимости. И из этого можно будет заключить, что в математике есть нерешённая задача – найти “сверхформулу Кардано”, которая позволит решить пятое уравнение аналитически.
Вообще-то, она решённая. Можно точно определить, когда уравнение имеет аналитическое решение в радикалах.

С точки зрения вычмата, есть ряд Штурма, который позволяет решить любой полином с заданной точностью за полиномиальное время (от степени полинома): https://ru.wikipedia.org/wiki/%D0%A0%D1%8F%D0%B4_%D0%A8%D1%82%D1%83%D1%80%D0%BC%D0%B0

Многие математические задачи могут быть решены в численном виде
Для решения в численном виде нужно:
— начальные условия
— граничные условия
— формула или функция или алгоритм перевода исходных данных в требуемые вычислить.

Любые формулы могут быть представлены численно в том или ином приближении.
Любые гладкие функции могут быть представлены в виде разложения в ряд слагаемых или множителей (с точностью до определенного члена). Доказана сходимость этих рядов, например разложить по синусам (ряд Фурье)

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

Здравствуйте, Bjorn Skalpe, Вы писали:

BS>Обратная задача восстановления функции — это разложение в ряд параметризованных множителей, т.е. по сути нейронная сетка, которая решает как раз обратную задачу восстановления весов ряда, т.е. гладкую функцию.

Разве то, что вы описали — это не решение системы линейных уравнений?

Нейронная сеть это вообще и есть система линейных уравнений (по крайней мере один слой нейросети).

Можно так же решать нелинейные х)

BS>Можно так же решать нелинейные х)

Хотелось бы подробнее.
Вы утверждаете, что существует универсальный алгоритм решения уравнения любой степени через нейросеть? А этот алгоритм эффективнее градиентного спуска?
Если степень уравнения 1, то прямая задача сводится к простой работе одного слоя нейросети. А если, например, это квадратное уравнение, то нейросеть становится двухслойной (или как правильнее назвать – двухранговой?)? А для кубического уравнения три слоя, и т.д.?