Для начала, в зависимости от того, как вы сформулируете проблему с самым длинным путем, на самом деле проблема может быть NP -твердой, но не NP -полной. NP -полная версия этой проблемы выглядит следующим образом:
Учитывая граф G и длину k, G имеет простой путь длины k или больше?
Эта проблема известна как NP -полная по причинам, о которых я расскажу позже.Однако эта тесно связанная проблема не на самом деле NP завершена:
Для данного графа G какой самый длинный простой путь в G?
Эта вторая проблема NP - трудная, но не NP - полная.Чтобы проблема была NP -полной, проблема должна быть проблема решения , проблема, ответом которой является логическое «да» или «нет».Однако эта вторая версия проблемы не является проблемой решения, поэтому она не может быть в NP , и поэтому она не может быть NP -комплектной.Вполне возможно, что ваш учитель думал об этом, когда говорил, что самая длинная проблема пути не является NP -полной, хотя я не могу сказать наверняка.
Что касается самой длиннойпроблема пути NP -полная, нам нужно обсудить два момента:
Эта проблема есть в NP .Интуитивно понятно, что есть эффективный способ проверить да, ответы на проблему.
Эта проблема NP -hard.То есть, существует NP трудная проблема, которая сводится к ней.
Для пункта (1) интуиция заключается в том, что если ответ на вопрос "даету этого графа есть простой путь длиной 137 или больше?это «да», есть простой способ продемонстрировать это кому-то.Просто дайте им этот простой путь.Как только у них есть путь, им легко проверить, действительно ли он соответствует требованиям.(Теперь, обнаружив , что этот путь может быть действительно трудным. Но как только мы каким-то образом изолируем его, нетрудно убедить людей в том, что он работает.)
Для пункта (2),Общий способ сделать это - начать с существующей NP -трудной проблемы и свести ее к нашей проблеме.Здесь мы начнем с задачи о гамильтоновом пути, которая заключается в следующем:
Учитывая граф G, существует ли простой путь, который проходит через каждый узел в G один раз и ровно один раз?
Вот как мы сводим эту проблему к проблеме самого длинного пути.Начните с графа G. Теперь задайте вопрос: есть ли в G простой путь длиной не менее n - 1, где n - количество узлов в G?Если это так, то этот простой путь должен посещать каждый узел один раз и ровно один раз, поскольку в противном случае на пути недостаточно узлов, чтобы его длина была не менее n - 1. И наоборот, если нет, то нет гамильтонова пути,поскольку любой гамильтонов путь будет соответствовать всем требованиям.Следовательно, если мы сможем эффективно решить проблему длинных путей, мы сможем эффективно решить проблему гамильтоновых путей.Поскольку проблема гамильтонова пути является NP -твердой, то и самая длинная проблема пути.
Теперь, тот факт, что эта проблема является NP -полным, не означаетчто для него нет решения за полиномиальное время.Проблема P против NP до сих пор не решена, и мы не знаем, P = NP или P ≠ NP мы не можем сказать, существует ли алгоритм полиномиального времени для задачи с самым длинным путем.Что мы можем сказать, так это то, что никакие известные алгоритмы для него не работают за полиномиальное время (вы упомянули, что некоторые сайты утверждают, что у них есть алгоритмы полиномиального времени для этой проблемы, но это не звучит правильно;этот алгоритм будет миллионером).
Теперь можно задать дополнительный вопрос: почему проблема с гамильтоновым путем NP трудна?Обычный способ доказать это - начать с 3SAT и сделать умное сокращение на основе гаджетов.Это слишком долго, чтобы исследовать здесь, но большинство учебников по теории вступления (включая знаменитый учебник Сипсера) отлично объясняют это.