Proving PATH problem is not a NP-complete problem

Question

PATH refers to the question of whether a directed path exists from s to t in a graph G. I know that PATH∈P but I find it hard to prove that it's not an NP-complete problem. If this was proven somehow, would that mean P≠NP?

Answer 1

For a problem to be NP-complete:

• it needs to be NP-hard
• it needs to be in NP

For a problem to be NP-hard, it must be at least as hard as the hardest problems in NP. That means it must be possible to use an NP-hard problem to solve any other problem in NP in polynomial time.

We want to prove that PATH isn't NP-complete, but we already know it's in P, so it is definitely in NP too (trivially, every deterministic Turing Machine can be simulated by a non-deterministic Turing Machine).

Hence, the only way to prove that PATH is not NP-complete is proving that there is at least one NP problem that cannot be reduced to PATH in polynomial time. Unfortunately, you will find that this depends on the P vs NP open problem.

Proof by contradiction

Let us use the The Traveling salesman problem (TSP), which is an NP-complete problem that seems to be quite relevant to PATH. Assume that TSP reduces to PATH, i.e. there exists a polynomial time modification for instances of the TSP problem so that they could then be correctly solved by a PATH Turing Machine.

We know all P problems are reducible to each other in polynomial time. Also, we know all NP problems are reducible to TSP in polynomial time.

So by transitivity, all NP problems reduce to TSP, TSP would reduce to PATH, and PATH reduces to all other P problems. This yields P = NP = NP-complete.

PATH is an NP-complete problem if and only if P = NP = NP-complete.

Similarly, proving that PATH isn't an NP-complete problem would be equivalent to proving P ≠ NP ≠ NP-complete. If PATH isn't an NP-complete problem, then no problem in P is, because all P problems are reducible to each other in polynomial time.