4 ms·
To verify the shortest path, you would need to compute all the other paths as well, to be sure. so this doesn't sound like NP-complete
by Yajirobe 5y ago
To verify the shortest path, you would need to compute all the other paths as well, to be sure. so this doesn't sound like NP-complete
- jcla1 5y agoThis confusion is caused by the different notions of problem: there are "decision" problems and "functional" problems. What grandparent asked ("what is the shortest path?") is a functional problem in nature, whereas P & NP are classes of decision problems. A (more or less) equivalent decision problem version of above question would be "is there a path of length at most X?", which then is of course easy to verify if a potential solution is presented.