I’m a bit confused too, but I found a Ph.D. thesis that answers a bunch of these questions. I’m still reading it.
On page 5, it says that for TSP, the question “Is the optimal value equal to k” is D^P-complete (which is something I haven’t heard of before).
I’m a bit confused too, but I found a Ph.D. thesis that answers a bunch of these questions. I’m still reading it.
On page 5, it says that for TSP, the question “Is the optimal value equal to k” is D^P-complete (which is something I haven’t heard of before).