Объясните пожалуйста как можно подробнее , что такое Р задачи , NP (полные , сложные ..) задачи . А то почитав так и не понял. Спасибо заранее
-
Подробнее Вам тут вряд ли расскажут, в Интернете полным-полно описаний, а ХэшКод - не для этого. А вот кратко, с чего начать - вполне– Михаил М12 ноя 2013 в 6:37
-
Хороший ответ по теме вопроса на братском подсайте: math.hashcode.ru/questions/35138#35141– VladD27 мар 2014 в 11:11
1 ответ
Смотрите, речь идёт об асимптотической сложности задач. Здесь рассматриваются только задачи, которые имеют простой однозначный ответ: «да» или «нет». Например, «есть ли подстрока "XYZ" в данной строке?». Задачи типа «найдите все перестановки данного набора чисел» как P/NP-проблемы не рассматриваются, так как ответ тут не да/нет.
Алгоритмы часто параметризуются размерами входных данных. Время пробега алгоритма в общем случае тем больше, чем больше данных ему приходится обрабатывать. Обозначим n1, n2, ... — параметры, описывающие размеры входных данных, t(n1, n2, ...)
— максимальное время работы алгоритма на данных такой длины.
Если известно, что t(n1, n2, ...)
ограничено сверху многочленом от переменных n1, n2, ...
, задача называется решаемой за полиномиальное время. Класс таких задач и обозначается как P, они считаются вычислительно несложными.
Теперь, что же такое NP-проблема?
Представьте себе, что у вас есть алгоритм с несколькими ветвлениями (if
-ами, циклами), который последовательно тестирует решения, и как только найдёт подходящее, сразу заканчивает алгоритм с криками «ура, нашёл!» Например, если мы ищем, есть ли символ 'X'
в данной строке, мы можем поочерёдно в цикле проверять, совпадает ли первый символ с X
, затем второй, затем третий, и как только нашли совпадение, заканчиваем работу. Так вот, представьте себе теперь такую машину, которая магическим образом сразу переходит к нужной итерации цикла: для поиска символа X
в строке "ABCXYZ"
она сразу проверяет в 4-ой позиции, то есть там, где надо! Такая магическая машина называется недетерминированной машиной (по историческим причинам) и, понятно, не существует в природе.
Так вот, проблема называется NP-проблемой, если она решается за полиномиальное время на этой самой читерской недетерминированной машине.
Понятно, что всякая P-проблема есть NP-проблема: если уж мы на нормальной машине решим её за полиномиальное время, то на читерской тем более! Возникает вопрос: а нужно ли читерство? Может быть, всякая проблема, которая решается на недетерминированной машине за полиномиальное время, может быть решена и на нормальной тоже за полиномиальное время?
Это и есть знаменитая P/NP-гипотеза: предполагают, что есть проблемы, которые без недетерминированной машины за полиномиальное время не решить. Но никто пока не смог это строго математически обосновать. Проблема тут вот в чём: если мы не умеем решать какую-то задачу за полиномиальное время, значит ли это, что она в принципе за полиномиальное время не решается, или мы просто недостаточно умны и изобретательны?
-
-
@VladD, а что за задачи, которые не решаются за полиномиальное время? Имхо, любую вычислительную задачу можно вычислить за полиномиальное время, пусть хоть и полином получится с очень высокими коеффициентами.– PaulD2 дек 2014 в 7:26
-
@SoloMio: Например, на текущий момент неизвестен полиномиальный алгоритм, который выясняет, изоморфны ли два графа (то есть, можно ли перенумеровать вершины у одного, чтобы он стал одинаковым со вторым). Вот большой список. Не исключено, что эти проблемы таки решаются за полиномиальное время, если да, то P == NP. (Это тогда потянет на результат десятилетия в computer science.)– VladD2 дек 2014 в 10:48
-
@VladD, еще такой вопрос, почему нельзя проэмулировать принятие за один шаг сразу нескольких решений с помощью многопоточности?– PaulD2 дек 2014 в 12:25
-
3Насколько я понимаю, вот такую одновременную проверку всех путей и выбор из них правильного (т.е. решения) нам обещают сделать в квантовом компьютере .– avp2 дек 2014 в 21:32