Question

We generally believe that PATH is not NP-complete. Explain the reason behind this belief. Show that proving PATH is not NP-complete would prove P ≠ NP

Short answer

If PATH is not NP -complete, then$NP\ne P\$.$

Step-by-step solution

To assume PATH would ne NP-complete

EveryAisNPis polynomial time reducible toB.

G is a directed graph that has a directed path.

PATH is not NP - complete:

Let us assume that PATH would be NP - complete.

From the definition of NP - completeness,

To explain it’s true or not

Thus$P=NP$ which we believe that it is not true.

Hence, PATH is not NP - complete.

Assume that$P=NP$ and then show that PATH is NP - complete.

So assume $P=NP$.

So, PATH is NP - complete.

Thus, if PATH is not NP -complete, then$P\ne NP$