4 ms·
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 op
by oefrha 2y ago
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.
- thaumasiotes 2y ago> 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?