Прямые и обратные задачи

[B3LYP]

Я имею отношение к квантовой и структурной химии, и слышал как люди, занимающиеся газовой электронографией, употребляли фразу “квантовики решают прямую задачу, а мы увы обратную”. Эта фраза мне понятна: расчёт изначально находит структуру и другие свойста, а в электронографии структура определяется через МНК (градиентный спуск) по экспериментальным данным. Хотя и в квантовой химии задачи “не до конца прямые”.

В действительности же, по-моему, любые задачи в математике в той или иной степени обратные, и вообще вся математика посвящена решению обратных задач. Возьмём для примера пять уравнений:

$ax+b=0$
$ax^2+bx+c=0$
$ax^3+bx^2+cx+d=0$
$ax^4+bx^3+cx^2+dx+e=0$
$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) Ещё одна связь между прямой и обратной задачей: существуют очень простые и универсальные методы решения обратной задачи через прямую, в частности простой перебор или градиентный спуск.

Теперь я предлагаю такую идею: взять пять уравнений выше и определить для них сложность решения обратной задачи. Сложность решения задачи можно измерить количественно – количеством машинного времени, потраченного на её решение с применением наилучшего алгоритма.

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

У меня ещё вопрос такой: какие бывают принципиальные виды подходов, позволяющие решать обратную задачу, если известно как решать прямую? Я вижу три таких подхода – простой перебор, градиентный спуск, и ещё может быть итерационное решение по теории возмущений. Что ещё знаете?

[Утундрий]

А почему вы не учитываете цвет? Прямые задачи красноватого оттенка, а обратные, наоборот, синенькие.

[Booker48]

А для логарифмирования/потенцирования что есть прямая, а что обратная задача?
Или для синуса/арксинуса?

[B3LYP]

Booker48 в сообщении #1700982 писал(а):

А для логарифмирования/потенцирования что есть прямая, а что обратная задача?
Или для синуса/арксинуса?

Ну я сам не в курсе - посчитать экспоненту легче чем логарифм? Посчитать синус легче чем арксинус?

[Booker48]

B3LYP в сообщении #1700985 писал(а):

Ну я сам не в курсе - посчитать экспоненту легче чем логарифм? Посчитать синус легче чем арксинус?

Ну, и там, и там - или таблица Брадиса, или бесконечный ряд.)))

[B3LYP]

Полагаю, подходы которые я тут описал, могут быть полезными в ИТ. Скажем, если говорить об искуственном интеллекте, работа нейросети - это решение прямой задачи, а обучение нейросети - это решение обратной задачи.
Вот ещё пример идеи, на которую меня натолкнула эта тема. У программистов есть понятие ассерта, это специально вставленный блок в программе, который проверяет что-то вроде самосогласованности массивов. Я предлагаю делить асссерты на "лёгкие" и "тяжелые"; тяжёлые долго выполняются, но проверяют всё разом.

[B3LYP]

Я всё пытаюсь скрипеть мозгами, в попытках понять, что такое шифрование с открытым ключом (оно же асимметричное шифрование). Вот приведу некую догадку-аналогию. Предположим, Алиса хочет передать Бобу сообщение 12, Ева читает всю их переписку. Боб вначале загадывает два простых числа, скажем 5 и 7. Если он их перемножит, он получит 35; и если бы он не боялся Евы, он бы просто передал Алисе это число, та бы сложила 12 с 35 и получила 47, передала 47 Бобу, тот бы вычел 35 из 47 и получил бы 12. Но чтобы Ева не перехватила сообщение, Боб передаёт Алисе только число 5, а 7 Ева не знает. Алиса производит какое-то преобразование над 12 с помощью числа 5, и передала результат Бобу; и тут сработает момент, что это преобразование с помощью 5 "портит" 12, так что без квантового компьютера восстановить 12 нельзя (даже зная 5), а вот зная и 5 и 7 - можно. Я верно рассуждаю?
И вот почему я задал вопрос в этой теме: какие можно перечислить примеры, когда решение обратной задачи настолько сложнее с вычислительной точки зрения, чем решение прямой задачи, что это можно использовать в криптографии (или уже используется)? Т.е. найти y по x легко, а найти x по y неизмеримо труднее.

[warlock66613]

Уравнение пятой степени прекрасно решается аналитически. Например:

вики: Корень Бринга писал(а):

Джордж Джеррард показал, что все уравнения 5-й степени могут быть решены в радикалах и корнях Бринга.

[mihaild]

Например, поиск квадратного корня как решения уравнения $x^2 - a = 0$ методом Ньютона - довольно эффективно. Чем поиск тем же методом Ньютона корня уравнения пятой степени хуже?

Вообще, неразрешимость уравнений выше четвертой степени в радикалах - это просто свойство выбранных базисных функций. Ничего особо фундаментального в этом наборе нет.

B3LYP в сообщении #1720738 писал(а):

Я всё пытаюсь скрипеть мозгами, в попытках понять, что такое шифрование с открытым ключом (оно же асимметричное шифрование).

Я бы советовал прочитать полное описание алгоритма и посчитать всё руками по шагам на листочке. Думаю, это будет существенно эффективнее, чем пытаться переизобрести, зная только что там есть какое-то умножение.

B3LYP в сообщении #1720738 писал(а):

И вот почему я задал вопрос в этой теме: какие можно перечислить примеры, когда решение обратной задачи настолько сложнее с вычислительной точки зрения, чем решение прямой задачи, что это можно использовать в криптографии (или уже используется)?

Это называется "односторонняя функция" - такая функция $f$, что вычислить $f(x)$ можно за полиномиальное от длины $x$ время, но для любой полиномиально вероятностно вычислимой функции $g$, $P_x(f(g(f(x))) = f(x))$ - вероятность по случайному $x$ длины $n$ и по результатам $g$ - убывает быстрее любого полинома от $n$.
Вопрос существования односторонних функций открыт. Если $P = NP$, то их не существует. Есть гипотеза, что умножение простых чисел (только нужно соответственно в качестве аргумента брать не строки, а пары простых чисел подходящих длин) - односторонняя функция.

[Anton_Peplov]

Видимо, B3LYP называет аналитическим решение в элементарных функциях, что ИМХО неудачно.

B3LYP в сообщении #1720738 писал(а):

Я всё пытаюсь скрипеть мозгами, в попытках понять, что такое шифрование с открытым ключом (оно же асимметричное шифрование)

ОМГ, Вам уже книжку, где все расписано по шагам, посоветовали. Ну возьмите и зашифруйте чего-нибудь короткое, а потом расшифруйте.

По стартовому посту. В функциональном анализе есть строгое определение обратной задачи для дифференциального уравнения. Есть и неформальное понимание, выходящее далеко за рамки дифуров, но достаточно расплывчатое. Неформальное понимание такое. Прямая задача: "У нас есть зверь, как он будет себя вести?". Обратная задача: "У нас есть поведение, что это за зверь, который так себя ведет?". Рассчитать, как будет выглядеть в телескоп термоядерный взрыв белого карлика - прямая задача. Определить, является ли вот эта наблюдаемая вспышка термоядерным взрывом белого карлика (aka сверхновая Ia), или сверхновой другого типа, или столкновением нейтронных звезд, или приливным разрушением звезды черной дырой, или битым пикселем на матрице - обратная задача. Хрусталик, проецируя трехмерные предметы на двумерную сетчатку, решает прямую задачу. Мозг, реконструируя трехмерное пространство по двумерной проекции - обратную. Как правило, обратные задачи сложнее прямых и не всегда они имеют решение, тем более единственное.