Индийский математик решил одну из задач тысячелетия
Коментариев: 0
Рейтинг: - | -
Добавлено: 11.08.2010
Индийский математик Винэй Деолаликар заявил, что ему удалось разгадать одну из задач тысячелетия. В качестве доказательства он предоставил статью на 100 страниц, где сделал вывод, что классы сложности P и NP не равны. Вопрос о равенстве классов сложности P и NP можно сформулировать следующим образом: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Решение данной задачи крайне важно для прикладных наук и компьютерных вычислений. Например, если можно быстро проверить, является ли правильным введенный шифр, то можно ли так же быстро взломать шифр? Винэй отвечает отрицательно на поставленные вопросы, объясняя это тем, что проверка шифра и его подбор относятся к задачам разного уровня сложности.