Для того, чтобы задача была NP-полной:
- должно быть NP-hard
- должно быть в NP
Чтобы задача была NP-сложной, она должна быть как минимум такой же сложной, как и самая сложная в NP.
Это означает, что должна быть возможность использовать NP-сложную задачу для решения любой другой проблемы в NP за полиномиальное время.
Мы хотим доказать, что PATH не является NP-полной, но мы уже знаем, что она в P, поэтому она определенно также в NP (тривиально, каждая детерминированная машина Тьюринга может моделироваться недетерминированной машиной Тьюринга).
Следовательно, единственный способ доказать, что PATH не является NP-полным, - это доказать, что существует по крайней мере одна проблема NP, которая не может быть уменьшена до PATH за полиномиальное время.
К сожалению, вы обнаружите, что это зависит от проблемы открытия P против NP.
Доказательство от противного
Давайте воспользуемся задачей коммивояжера (TSP), которая представляет собой NP-полную проблему, которая, по-видимому, весьма актуальна для PATH.
Предположим, что TSP сводится к PATH, т. Е. Существует полиномиальное изменение времени для экземпляров проблемы TSP, чтобы затем их можно было правильно решить с помощью машины Тьюринга PATH.
Мы знаем, что все P-проблемы сводятся друг к другу за полиномиальное время.
Кроме того, мы знаем, что все проблемы NP сводятся к TSP за полиномиальное время.
Таким образом, благодаря транзитивности все проблемы NP сводятся к TSP, TSP сводится к PATH, а PATH сводится ко всем остальным проблемам P.
Это дает P = NP = NP-завершено.
PATH является NP-полной проблемой тогда и только тогда, когда P = NP = NP-complete.
Аналогично, доказательство того, что PATH не является NP-полной проблемой, будет эквивалентно доказательству P ≠ NP ≠ NP-полной. Если PATH не является NP-полной проблемой, то нет проблем в P, потому что все P проблемы сводятся друг к другу за полиномиальное время.