Знакомые с наукой люди слышали об одной из самых больших проблем математики – так называемой «проблеме равенства классов P и NP». Но это не просто странная математическая головоломка. Человек, который ее решит, мгновенно станет на миллиарды долларов богаче, ведь он сможет повелевать всеми криптовалютами. И сможет, например, присвоить все Bitcoin в мире.
Важность проблемы P vs NP показывает то, что ее включили в одну из семи задач в списке «Задачи тысячелетия» (Millennium Prize Problems)». За решение такой задачи кембриджский Математический институт Клея выдает $1 млн. Но это мелочь по сравнению с тем, какие возможности открываются в случае, если P = NP.
«Если кто-то докажет, что P = NP, первая вещь, которую они должны сделать, – украсть $200 млрд в Bitcoin, – говорит ученый Скотт Ааронсон. – Вторая вещь, которую они должны сделать, – решить все остальные задачи списка «Задачи тысячелетия».
В общем проблему равенства P = NP можно описать так: если утвердительный ответ на вопрос можно достаточно быстро проверить, то правда ли, что ответ на этот вопрос можно достаточно быстро найти. Если совсем коротко: действительно ли решение задачи проверить не легче, чем его отыскать?
Последствия, если окажется P = NP, будут масштабными из-за особенности работы компьютеров. Для расчета задач процессор выполняет набор шагов. Чем сложнее задача, тем больше шагов нужно. Символом «P» обозначают задачи, которые компьютеры решают постоянно: от умножения чисел к серфингу в интернете. С ростом сложности задачи время для ее решения возрастает полиномиально, то есть в несколько раз быстрее.
Существует много проблем, для которых можно быстро оценить правильность предложенного решения. Однако отыскать это решение потребует значительно больше времени. Такой тип задач называется недетерминированное полиномиальное время (Nondeterministic Polynomial time), или проблемы NP. С такими задачами знаком почти каждый. Например, судоку является NP-проблемой – сложно решить, легко проверить.
Основой криптографии современных компьютеров является задача NP – разложение очень больших чисел на простые числа. Сейчас на это нужно очень много времени, но проверить разложения просто – нужно лишь перемножить предложенные простые числа. Криптография, в свою очередь, является основой для виртуальных денег, включая Bitcoin.
Ожидалось, что рывок в задачах P и NP дадут квантовые компьютеры, которые смогли бы быстро решать самые сложные задачи NP и открыть путь к решению любых задач NP. Но хайп прошел, и человечество продолжает пользоваться обычными кремниевыми процессорами, а квантовый компьютер все еще диковинка, которая решает очень ограниченный круг задач. Впрочем, еще рано терять надежды: прогнозируется, что блокчейн Bitcoin сломают где-то до 2027 года.
По материалам: Gizmodo
