Let's say I have a PATH as so...

$$PATH = {G, s, t}$$

Where G is a directed path from $s$ to $t$. Apparently this is considered not NP-Complete. I fail to see why. Can someone explain?

  • $\begingroup$ The term "NP-complete" is used about certain decision problems, and you don't seem to be describing any decision problem at all ... $\endgroup$ – hmakholm left over Monica Nov 28 '17 at 6:47

NP-completeness is a property of decision problems, not graphs or paths. I'm going to guess and say that $PATH$ refers to the question of whether a directed path exists from $s$ to $t$ in the graph $G$. This can be done with e.g. a depth first search, which has time complexity $O(|V|+|E|)$, polynomial in the number of vertices. Based on current understanding of complexity theory, problems that can be solved in polynomial time are not NP-complete, because that would mean problems that are widely considered unsolvable in polynomial time could be reduced to $PATH$ in polynomial time and then solved in polynomial time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.