Вопрос o равенстве классов сложности P и NP решен?
Добавлено: 11 авг 2010, 12:15
Индийский математик Винэй Деолаликар (Vinay Deolalikar) представил доказательства решения одной из так нызываемых задач тысячелетия, - ученый опубликовал 100-страничную статью, в которой сделан вывод, что классы сложности P и NP не равны. O работе пишет New Scientist.
Вопрос o равенстве классов сложности P и NP можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Эта задача чрезвычайно важна для компьютерных вычислений и прикладных наук, в частности для наук o шифровании данных. Например, если можно быстро проверить, является ли введенный шифр правильным, то можно ли достаточно быстро взломать этот шифр?
B течении недели экспертное сообщество проведет оценку доказательства дабы прийти к однозначному мнению относительно статьи Деолаликара
Вот, собственно, и сама ссылка на эту инфу (не на доказательство!)
[url=http://arvo.ua/index.php?event=show_news&a...z=9&id=5058]http://arvo.ua/index.php?event=show_news&a...z=9&id=5058[/url]
Вопрос o равенстве классов сложности P и NP можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Эта задача чрезвычайно важна для компьютерных вычислений и прикладных наук, в частности для наук o шифровании данных. Например, если можно быстро проверить, является ли введенный шифр правильным, то можно ли достаточно быстро взломать этот шифр?
B течении недели экспертное сообщество проведет оценку доказательства дабы прийти к однозначному мнению относительно статьи Деолаликара
Вот, собственно, и сама ссылка на эту инфу (не на доказательство!)
[url=http://arvo.ua/index.php?event=show_news&a...z=9&id=5058]http://arvo.ua/index.php?event=show_news&a...z=9&id=5058[/url]