Разница между NP трудной и NP полной проблемой
Предпосылка: NP-полнота
НП Проблема:
Задачи NP - это набор проблем, решения которых трудно найти, но легко проверить и которые решаются недетерминированной машиной за полиномиальное время.
NP-сложная проблема :
Проблема X является NP-сложной, если существует NP-полная проблема Y, такая что Y сводится к X за полиномиальное время. Проблемы NP-Hard так же сложны, как и задачи NP-Complete. NP-Hard Проблема не обязательно должна быть в классе NP.
NP-полная проблема :
Проблема X является NP-полной, если существует NP-проблема Y, такая что Y сводится к X за полиномиальное время. Проблемы NP-Complete так же сложны, как и задачи NP. Задача является NP-полной, если она является частью как NP-задачи, так и NP-Hard. Недетерминированная машина Тьюринга может решить NP-полную задачу за полиномиальное время.
Разница между NP-Hard и NP-Complete : NP-жесткий NP-Complete NP-трудные проблемы (скажем, X) могут быть решены тогда и только тогда, когда существует NP-полная проблема (скажем, Y), которая может быть сведена к X за полиномиальное время. NP-полные задачи могут быть решены аннон-детерминированным алгоритмом / машиной Тьюринга за полиномиальное время. Чтобы решить эту проблему, не обязательно быть в НП. Чтобы решить эту проблему, это должны быть как NP, так и NP-сложные задачи. Не обязательно должна быть проблема с Решением. Это исключительно проблема решения. Пример: проблема остановки, проблема вершинного покрытия, проблема выполнимости схемы и т. Д. Пример: определить, есть ли в графике гамильтонов цикл, определить, выполнима ли булева формула и т. Д.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.