Объясните пожалуйста как можно подробнее , что такое Р задачи , NP (полные , сложные ..) задачи . А то почитав так и не понял. Спасибо заранее
Ответ
Смотрите, речь идёт об асимптотической сложности задач. Здесь рассматриваются только задачи, которые имеют простой однозначный ответ: «да» или «нет». Например, «есть ли подстрока "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-гипотеза: предполагают, что есть проблемы, которые без недетерминированной машины за полиномиальное время не решить. Но никто пока не смог это строго математически обосновать. Проблема тут вот в чём: если мы не умеем решать какую-то задачу за полиномиальное время, значит ли это, что она в принципе за полиномиальное время не решается, или мы просто недостаточно умны и изобретательны?
Комментариев нет:
Отправить комментарий