Лет 5 назад вычитал в википедии про крупные задачи в математике за которые дают еще и миллион долларов.

Одну там Перельман решил еще недавно, помните и отказался от денег.

И там среди них есть одна задача, которая меня заинтересовала - проблема равенства классов сложности P и NP.

Чтобы весь пост не объяснять детально, попробую основное объяснить - суть в том, чтобы доказать что сложные задачи можно решать также просто как и простые задачи, либо доказать, что нельзя.

Это очень грубое пояснение, но суть примерно верна. Основным мерилом простоты задачи считается, то насколько быстро компьютер может ее посчитать. Как на картинке P - операция умножения - это за секунду считается самым дешевым калькулятором. NP - в примере судоку, тут уже может быть нужен более мощные процессор и больше времени.

Я прям очень увлекся одно время этой задачей, и в качестве практического примера сложной задачи для которой можно найти простое решение рассматривал алгоритм шифрования.

Шифрование само по себе быстро происходит, часть ключа получается из перемножения двух 2048-значных чисел. Это простая задача. А вот получиться обратно из результата перемножения два множителя - это намного более сложная задача, поэтому шифрование и относительно безопасно - злоумышленникам нужны большие вычислительные мощности чтобы перебрать варианты множителей.

В общем я к чему. Миллион долларов я не получил, как вы поняли, но в задаче продвинулся немного. У Ферма есть алгоритм как раз для похожей задачи Метод факторизации Ферма - поиск множителей.

И тогда несколько лет назад, я его математическую логику воплотил в код калькулятора и повыполнял на разных числах.

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

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

Такая неточность/ненадежность алгоритмов сначала показалась мне тупиком и я дальше не стал развивать исследование.

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

Один из ранних примеров для меня это быстрый обратный квадратный корень Кармака - посчитать симуляцию света в игре на железе тех лет было очень дорого, поэтому он считал приближенно, и это было прорывом и свет все равно прикольно выглядел, даже пусть и неточно считался. В случае компьютерной игры это допустимо.

А теперь когда везде ИИ я прямо прозрел. Вот же она самая проблема P и NP и мои наблюдения о приближенных вычислениях теперь повсюду.

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

Если бы я знал как эти мысли еще оформить в математический язык, то может быть и получил бы миллион долларов, что думаете?

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

Можно притянуть приближенное решение в качестве аргумента, что P = NP? наверное нет. Но наверное можно вместо равно поставить другой знак P ≈ NP - вот и решение проблемы на миллион долларов.