Okay apparently my complexity theory is rusty and I’m remembering results but not remembering the reasons for those results, so sorry about that. Determining optimal path length to a certain degree is indeed in the same class as the decision problem. It’s finding that optimal path (optimization problem) that’s not NP-complete.
> It’s finding that optimal path (optimization problem) that’s not NP-complete.
I'm having some trouble with this. As far as I can see, finding a path of a given maximum length must be in NP, because it's very easy to deterministically verify that a given path has length no more than the maximum.
If determining the optimal path length is in NP, and identifying a path of that length is also in NP, how can determining an optimal path fail to be in NP?
