Вот аналогия.Я хочу убедить вас, что Супермен обладает невероятными сверхчеловеческими способностями.Для этого я говорю вам, что он быстрее пули.«Быстрее пули?» - говорите вы.«Это действительно быстро!Ни один человек не может этого сделать - это действительно тяжело! »
Теперь я скажу вам больше - он не только может бежать быстрее, чем пуля с ускорением;он может прыгать с высоких зданий одним прыжком.«Вау!», - вы, вероятно, сказали бы, - «это тоже очень сложно!Но опять же, я уже знал, что Супермен может делать действительно сложные вещи, потому что вы сказали мне, что он может бежать быстрее, чем пуля с ускорением ». В этом смысле, сказав, что Супермен может сделать одну сложную вещь, я уже убедил вас, что ондовольно сильныйТо, что он может делать и другие сложные вещи, не меняет этого.
Теперь давайте поговорим о самых длинных путях.Причина, по которой проблема самого длинного пути является NP-трудной, состоит в том, что для любого графа вы можете назначить каждому ребру в этом графе длину единицу, а затем проверить, имеет ли этот новый граф простой путь длины n - 1. Это действительноЭто трудно сделать, потому что, как мы знаем, проверить, есть ли у графа гамильтонов путь, действительно сложно.(Это бит «Супермен может бежать быстрее, чем ускоряющая пуля».)
Теперь представьте, что мы говорим: «Эй, я не только могу решить эту проблему с положительными весами, но я также могу решить эту проблему, есливесовые коэффициенты также могут быть отрицательными! »С вашей точки зрения, я не облегчил задачу поиска длинных путей.Мы все еще можем использовать то же сокращение, что и раньше, чтобы найти гамильтоновы пути.Это также случай, когда мы можем делать и другие вещи.(Это бит «может перепрыгивать высокие здания за один прыжок».)
В общем, если вы начинаете с NP-сложной задачи, а затем обобщаете ее, у вас обычно остается NP-сложная задача.проблема, потому что в этой проблеме все еще есть все сложные биты, а также куча новых случаев, которые ей необходимо обработать.