"Задача на миллион" ставит под вопрос надежность криптозащиты

Вкратце вопрос о равенстве или неравенстве классов сложности P и NP сводится к следующему: P - это класс задач, решение которых (относительно) легко найти, класс NP включает задачи, для которых легко проверить, является ли предлагаемое решение верным. Правда ли что задачи, которые просто проверить, можно легко решить?

Это не первая попытка решить вопрос о равенстве P и NP классов, и некоторые исследователи скептически относятся к новому доказательству. Скотт Ааронсон (Scott Aaronson), исследователь из MIT, и другие ученые указывают на изъяны в работе, которые могут оказаться для нее фатальными.

По мнению Ричарда Липтона (Richard Lipton), исследователя из Технологического института Джорджии, работа Долаликара, даже если ученому не удастся доказать свой основной тезис, по крайней мере, приближается к доказательству так, как ни одно из предшествующих исследований на эту тему. И потерпев провал, все равно проложит путь к решению проблемы будущим исследователям.

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

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

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

С 70-х годов прошлого века исследователи занимаются проблемой равенства классов сложности P и NP. Основной вопрос: существует ли в NP-проблемах некий скрытый порядок, который сделает их легкими для решения. Если бы задачи NP-типа оказались равны по сложности задачам P-типа, это означало бы, что существует универсальное решение множества задач, с которыми раньше не мог справиться компьютер. В качестве примера можно привести задачу складывания белков в компьютерной игре FoldIt, это также позволило бы оптимизировать такие сложные процессы, как международные перевозки. Однако с другой стороны, если P=NP, это означает, что в своей основе все криптосистемы, используемые нами каждый день, легко взломать.

Деолаликар в своей работе доказывает, что проблемы NP-типа не могут быть так легко решены, как проблемы P-типа.