Одна из задач тысячелетия - проблема равенства классов P и NP


Итак, в чем отличие классов P и NP? Нестрого говоря, P - это класс задач, в

которых нужно проверить, удовлетворяет ли данное решение условиям, а NP -

класс задач, в которых нужно найти удовлетворяющее условиям решение.

Например, задача "Дана раскраска вершин произвольного графа в три цвета.

Проверить, является ли она правильной (т.е нет ли смежных вершин, окрашенных

в один цвет)" из класса P, а задача "Найти правильную раскраску произвольного

графа в три цвета (замечу, что решения может не существовать вовсе)" из

класса NP. (Граф - это множество вершин (точек) и ребер (линий, соединяющих

две вершины). Вершины, соединённые ребром, считаются смежными. Ниже есть

поясняющие рисунки с графами и раскраской). Помимо всего прочего, вторая

задача является так называемой NP-полной задачей. То есть если мы можем

решить её, то мы автоматически можем решить любую другую задачу из класса NP.

Да, равенство классов тут понимается в том смысле, что мы можем свести любую

задачу из NP к какой-то задаче из P (обратное уже доказано). Главный смысл

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

можем.

Теперь что будет, если кто-то всё-таки докажет P=NP? Ну, любая существующая

сейчас криптосистема с открытым ключом станет очень сильно ненадёжной (задача

взлома - тоже NP-полная задача). Это из плохого. Из хорошего - мы научимся

быстро решать очень много важных задач. Например, в перспективе можно будет полностью вылечить некоторые вирусные болезни (грипп - в их числе).

Впрочем, большинство учёных сейчас не верит в то, что P=NP. В этом случае из

хороших следствий будет разве что радость всех тех, кто пользуется

вышеупомянутой криптосистемой (если кто-то знает ещё что-нибудь - пишите).

4
тут быстро не скажешь,но:<br />
могут существовать задачи класса P, которые не решаются быстро, при этом даже в случае равенства ничего плохого не произойдёт<br />
ну а вообще я этим не интересовался, всё что тут могу сказать, было в своё время прочитано в википедии
Demonolog, разве класс P не определяется как класс задач, которые решаются за полиномиальное время? Хотя тут, конечно, можно подобрать какие-нибудь мерзкие константы, и вообще &quot;быстро&quot; использовано очень нестрого, но всё же?
Талласа, время то полиномиальное, но на практике есть ещё время ввода и вывода результатов, которое за счёт большого количества данных очень велико, узнал я это, когда прочитал про тест Агравала — Каяла — Саксены для определения простоты чисел<br />
на практике всё будет ок
Demonolog, и это тоже, видимо. Я вспомнила, можно же ещё свести задачу из NP к задаче из P как-нибудь криво и ужасно, это тоже потребует время. И ещё ограничение по памяти...
× Пришло новое сообщение