Учёный индийского происхождения Винай Деолаликар, работающий в Кремниевой долине, умудрился собрать доказательства для того, чтобы вслед за российским математиком решить ещё одну из семи задач тысячелетия.
В Интернете появилась сначала вот эта формула: "P не равно NP". Те, кто серьёзно занимается информатикой, сразу поняли, в чём дело, и принялись изучать остальные после титульного листа 97 страниц доказательств американского учёного.
Речь идет о задачах, которые оперируют большими массивами данных: имен, адресов, телефонов и т.п. – и решаются при помощи компьютерной техники. P – это класс задач, решение которых относительно легко найти: например, расположить в алфавитном порядке имена, положим, тысячи человек, найти, кто из них живет в одном городе, на одной улице, составить возрастную картину списка.
А вот класс NP включает такие задачи, для которых легко проверить, является ли предлагаемое решение верным. Например, у вас есть код, вы не знаете алгоритма кодирования, но можете легко проверить, какие комбинации не являются (или наоборот, являются) правильным кодом.
Вопрос, который еще в прошлом веке поставили перед собой математики, следующий: правда ли что задачи, которые просто проверить, в принципе, можно и легко решить? Или, правда ли, например, что компьютер – пусть, положим, только в будущем – можно будет научить легко взламывать коды.
Ответ "да" означал бы, что существует универсальное решение множества задач, с которыми раньше не мог справиться компьютер: и это не только щекотливые вопросы криптографии – что, понятно, далеко не всех может порадовать, – но и масса очень полезных задач, оптимизация международных перевозок, например.
Но американский математик дает ответ "нет". Осталось дождаться ответа от остальных групп учёных, которые должны тоже убедиться в его правоте. Как говорят математики, решение, по крайней мере, выглядит серьезно. Если это действительно так, то исследователь получает свой миллион от математического института Клэя, от которого, напомним, его питерский коллега отказался.
Программисты по всему миру примутся заламывать руки в отчаянье. Ведь многие задачи, которым надеялись при помощи суперкомпьютеров найти быстрое решение, и впредь останутся фундаментально сложными. А весь остальной мир сможет заснуть спокойно: шифрование останется действенным методом сохранить их информацию, передает телеканал "Роcсия 24".
