Why is that? In order for function minimization to be in NP, you have to be to write a polytime-checkable proof of the fact that some input is a minimum. I don’t think that’s true in general.
...That’s an interesting way to look at it. For example take the traveling salesman problem: it’s traditionally converted to a decision problem by asking if there’s a route cheaper than X. Note that only “yes” answers have to have quickly checkable certificates—this is NP, not NP intersected with co-NP. Now if we start asking if X is exactly the minimum instead, would that be equivalent in complexity? And would it be helpful, seeing as it takes away our ability to do binary search?
In short, I’m a little funny in the head right now, but still think my original claim was correct.
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 :-)
...That’s an interesting way to look at it. For example take the traveling salesman problem: it’s traditionally converted to a decision problem by asking if there’s a route cheaper than X. Note that only “yes” answers have to have quickly checkable certificates—this is NP, not NP intersected with co-NP. Now if we start asking if X is exactly the minimum instead, would that be equivalent in complexity? And would it be helpful, seeing as it takes away our ability to do binary search?
In short, I’m a little funny in the head right now, but still think my original claim was correct.
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 :-)
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).