This paper (which I found via this Ph.D. thesis) says that for TSP, the question “Is the optimal value equal to k” is D^P-complete. It also says D^P contains both NP and coNP, so assuming NP!=coNP, that problem is not in NP.
Your original claim was “If computing the function is in P, minimization is in NP.” Technically, this sentence doesn’t make sense because minimization is a functional problem, whereas NP is a class of decision problems. But the ability to minimize a function certainly implies the ability to determine whether a value is a minimum, and since that problem is not in NP, I think your claim is wrong in spirit as well.
As Nesov pointed out, TSP is in FP^NP, so perhaps a restatement of your claim that is correct is “If computing the function takes polynomial time, then it can be minimized in polynomial time given an NP oracle.” This still seems to imply that function minimization isn’t much harder than NP-complete problems.
Are there any problems in PostBQP that can be said to be much harder than NP-complete problems? I guess you asked that already.
I can’t read those links, but determining whether an input is a minimum seems to be in co-NP because it allows easy verification of a “no” answer by counterexample. So have those people proved that NP=co-NP, or am I just being dense?
This still seems to imply that function minimization isn’t much harder than NP-complete problems.
Yep, as a programmer I should’ve said “at most polynomially harder than a problem in NP”. You’re right that my wording was bad. I still stand by the spirit, though :-)
This paper (which I found via this Ph.D. thesis) says that for TSP, the question “Is the optimal value equal to k” is D^P-complete. It also says D^P contains both NP and coNP, so assuming NP!=coNP, that problem is not in NP.
Your original claim was “If computing the function is in P, minimization is in NP.” Technically, this sentence doesn’t make sense because minimization is a functional problem, whereas NP is a class of decision problems. But the ability to minimize a function certainly implies the ability to determine whether a value is a minimum, and since that problem is not in NP, I think your claim is wrong in spirit as well.
As Nesov pointed out, TSP is in FP^NP, so perhaps a restatement of your claim that is correct is “If computing the function takes polynomial time, then it can be minimized in polynomial time given an NP oracle.” This still seems to imply that function minimization isn’t much harder than NP-complete problems.
Are there any problems in PostBQP that can be said to be much harder than NP-complete problems? I guess you asked that already.
There was a dumb comment here, I deleted it. You’re actually completely right, thanks!
I can’t read those links, but determining whether an input is a minimum seems to be in co-NP because it allows easy verification of a “no” answer by counterexample. So have those people proved that NP=co-NP, or am I just being dense?
Yep, as a programmer I should’ve said “at most polynomially harder than a problem in NP”. You’re right that my wording was bad. I still stand by the spirit, though :-)