Индийский математик Винэй Деолаликар (Vinay Deolalikar) представил доказательства решения одной из так нызываемых задач тысячелетия, — ученый опубликовал 100-страничную статью, в которой сделан вывод, что классы сложности P и NP не равны. Препринт статьи в формате pdf можно скачать здесь, коротко о работе пишет New Scientist.
Вопрос о равенстве классов сложности P и NP можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Эта задача чрезвычайно важна для компьютерных вычислений и прикладных наук, в частности для наук о шифровании данных. Например, если можно быстро проверить, является ли введенный шифр правильным, то можно ли достаточно быстро взломать этот шифр?
КСТАТИ
За что еще дадут миллион долларов
1. Проблема Кука 2. Гипотеза Римана 3. Гипотеза Берча и Свиннертон-Дайера 4. Гипотеза Ходжа 5. Уравнения Навье - Стокса 6. Уравнения Янга - Миллса
Комментариев нет:
Отправить комментарий