Как захватить мир, доказав, что P=NP

Ничего не выйдет, если доказательство будет неконструктивным. Представьте, что вы найдёте какое-нибудь отражение алгоритмов на топологию, а потом используя неразрывные потоки на многомерных сферах докажете эквивалентность P и NP.

Это никак не поможет строить P алгоритмы для NP задач.

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

Какой милый и добрый захватчик мира! Взял денег и всех вылечил. А потом еще и секретом поделился! Хочу жить в мире, где такие злодеи…

А если серьезно — интереснее, что делать с криптографией после того, как такой гений обнаружится? Ведь, как я понимаю, большая часть шифровальных алгоритмов построена именно на вере в неупрощаемость вычислений, так? Не будет больше математической криптографии? Снова будем ценности и тайны в землю закапывать?

Как захватить мир, найдя философский камень?

Зачем деньги воровать то?
Вроде бы подобрать заголовок биткоин блока вполне себе NP задача, которую мы и умеем решать.
Сейчас за блок дают 25 биткоинов по 570 долларов. 14 тысяч долларов, неплохо и легально. Ну и другие монетки.
Кстати, миллион долларов можно собрать быстрее чем институт Клея признает доказательство.

В плане P? NP можно вспомнить тест AKS (Агравала — Каяла — Саксены). Он был предложен в 2002 году, и позволил отнести проблему определения простоты числа к классу P. Однако, несмотря на полиномиальность, этот тест работает слишком медленно, за O(log^6 n) и на практике проблему продолжают успешно решать с помощью вероятностных алгоритмов.

teal.gmu.edu/courses/ECE746/project/F06_Project_resources/Salembier_Southerington_AKS.pdf

VIII.CONCLUSION The AKS algorithm in its current form is not suitable for general use due to the length of time required to verify primality.… Currently available probabilistic algorithms provide much faster response times within margins of error that are generally acceptable. Primality tests for numbers that might take hours or days using AKS could be performed in seconds or even less using probabilistic methods such as Miller-Rabin.

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

«AES… Он считается «золотым стандартом» шифрования. И вы доказали, что он бесполезен.» — здесь тоже есть проблема. Вне зависимости от равенства или неравенства классов P и NP, могут существовать или не существовать алгоритмы взлома AES более эффективные алгоритмы, чем полный перебор. Полиномиальные алгоритмы (если они есть) могут быть применимы для какого-либо AES-N, с огромной длиной ключа N (например, для ключей размером более 1 млрд бит). Такие алгоритмы будут совершенно неприменимы к AES-256.

www.schneier.com/blog/archives/2010/08/p_np_1.html

If P=NP, then there's a polytime algorithm for breaking AES-K, for keys of size K, that's polynomial in the limit as K goes to infinity.… So even if P=NP, it's still possible that AES-256 has no breaks other than brute force. It's even possible that AES-trillion has no breaks other than brute force. All P=NP would tell us is that we'll have something other than brute force for key lengths above SOME unknown threshold.

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

crypto.stackexchange.com/questions/6313/is-aes-reducible-to-an-np-complete-problem

AES is a finite-domain function. It is invertible / distinguishable from a random permutation in (large but) constant time. The definitions of P, NP, etc., refer to asymptotic behavior — that is, as the input size grows to infinity. Because of the algebraic structure of AES, it is probably possible to define a «generalized AES» for infinitely many key lengths....

Как отмечено в wiki (P_versus_NP_problem) для слома криптографии требуется не произвольное полиномиальное, а эффективное решение для NP-полных задач.

Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution[Note: Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of O(N^2) or better and a reasonable constant term would be catastrophic. On the other hand, a solution that is \Omega(N^4) or worse in almost all cases would not pose an immediate practical danger.] to an NP-complete problem such as 3-SAT would break most existing cryptosystems including:

Статья предлагает совершать вещи, которые требуют много разных квалификаций и которые одному человеку не под силу. Начиная от безнаказанного воровства денег. Вас быстро вычислят спецслужбы. Чтобы от них скрыться, нужно обладать квалификацией и изобретательностью, сравнимой с целым коллективом сотрудников спецслужб. Даже знаменитых хакеров ловят. А ведь они жизнь посвятили информационной безопасности, как в плане нападения, так и в плане защиты.

Как водится, любой миллиардер может рассказать историю любого своего миллиона… кроме первого.

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

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