Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Равенство классов P и NP, обьясните в чём суть этой теории?

Сергей Петров Мастер (1169), закрыт 11 лет назад
А также в чём ее ценность, ведь из неё по сути ничего полезного не извлечешь:) ну я так думаю)
Дополнен 13 лет назад
Желательно простым языком)
Лучший ответ
Богдан Шевченко Мастер (1963) 13 лет назад
Есть задачи, ответы на которые легко проверить, и понять, правильные они, или нет (например, тебе даны много чисел, и нужно выбрать 15 так, что бы их сумма была равна 100 - если у тебя есть ответ ты можешь легко проверить его правильность, сложив эти числа, и увидев получается 100 или нет)
Равенство Р и NP означает, что все задачи которые так легко можно проверить, можно решить достаточно быстро. Это то что написано выше, "полиномиальная сложность" - обычно сложность задач, таких как та, которую я привёл в пример, зависит от количества исходных элементов. Полиномиально - означает, что количество шагов в алгоритме решения прямо пропорционально количеству элементов, или их квадрату, или кубу и т. д. Это хорошо. А если они пропорциональны експоненте этого количества, это означает, что уже при тысяче элементов никто не решит такую задачу. Это плохо.
Я упрощал как мог)

А насчёт пользы, если P=NP, то любой шифр, например, можно взломать. А ещё смогут нормально просчитывать как скручиваются белки, и изобретут лекарство от рака и спида (не факт, конечно, но это не шутка)
Остальные ответы
Mikhail Levin Искусственный Интеллект (615712) 13 лет назад
нет такой "теории".
есть два класса задач - класс P - задачи, которые решаются за полиномиальное время,
и класс NP - задачи, которые эквивалентны задаче коммивояжера.

Можно ли решить задачи NP за полиномиальное время - неизвестно.

В чем ценность? В том же, в чем и ценность любой математической задачи. Она дает понимание. Ну а что потом где-то на практике пригодится - никому не известно.

Вот недавно выяснилось, что еще Гаусс придумал быстрое преобразование Фурье, но не опубиковал за ненадобностью. Через век его снова переоткрыли - и оно стало мощнейшим инструментом, без которого трудно представить и обработку звука и изображений, и криптографию, и мобильники, и банкоматы, и mp3, и dvd.

Zerax Ученик (149) 9 лет назад
Самое просто объяснение...

Суть проблемы NP... Решить задачу поиска не прибегая к методу поиска.
Sergo Lis Ученик (113) 7 лет назад
Это одна из 7 задач тысячелетия я ей мы сможем сделать научный прорыв и т. д
Похожие вопросы